Exercises from Section 1.2.6

Tord M. Johnson

May 7, 2015

1. [00] How many combinations of n things taken n 1 at a time are possible?

There are n n1 = n combinations of n things taken n 1 at a time. Intuitively, each distinct set of n 1 objects leaves out a single item, and there are n items.

2. [00] What is 0 0?

We have

0 0 = 0! 0!(0 0)! = 1 1 = 1.

Intuitively, there is only a single way to choose nothing from nothing.

3. [00] How many bridge hands (13 cards out of a 52-card deck) are possible?

There are 52 13 = 635013559600 possible bridge hands, as we are choosing 13 from 52 things.

4. [10] Give the answer to exercise 3 as a product of prime numbers.

The answer to exercise 3 was 52 13 = 52! 13!(5213)! = 52! 13!39!. We can use Eq. 1.2.5-(8) to determine the prime factorization of each factorial and then the answer as a whole as

52 13 = 52! 13!39! = 249 323 512 78 114 134 173 192 232 29 31 37 41 43 47 210 35 52 7 11 13 235 318 58 75 113 133 172 192 23 29 31 37 = 249 323 512 78 114 134 173 192 232 29 31 37 41 43 47 245 323 510 76 114 134 172 192 23 29 31 37 = 24 52 72 17 23 41 43 47.

5. [05] Use Pascal’s triangle to explain the fact that 114 = 14641.

By the binomial theorem,

114 = (10 + 1)4 = 0k4 4 k10k14k = 4 4104 + 4 3103 + 4 2102 + 4 1101 + 4 0100 = (1)104 + (4)103 + (6)102 + (4)101 + (1)100 = 14641.

That is, the digits represent the row in Pascal’s triangle for 4 k, 0 k 4.

6. [10] Pascal’s triangle (Table 1) can be extended in all directions by use of the addition formula, Eq. (9). Find the three rows that go on top of Table 1 (i.e., for r = 1, 2, and 3).

Using Eq. (9)

r k = r 1 k + r 1 k 1

we can extend Pascal’s triangle (Table 1) for r = 1, 2, and 3 as












rr 0r 1r 2r 3r 4r 5r 6r 7r 8r 9











-3 1 -3 6 -10 15 -21 28 -36 45 -55
-2 1 -2 3 -4 5 -6 7 -8 9 -10
-1 1 -1 1 -1 1 -1 1 -1 1 -1











since r 0 = 1, r 1 = r, and r1 k = r k r1 k1.

7. [12] If n is a fixed positive integer, what value of k makes n k a maximum?

Proposition. n k n n2 = n n2 for all integers n 1, k.

Proof. Let n, k be arbitrary integers such that n 1. We must show that

n k n n2 = n n2.

First, we must show that the binomial coefficient is monotone in k, 0 k n 2 . That is, that

n k 1 n k1 k n 2 .

But

k n 2 k n + 1 2 2k n + 1 k n k + 1 k n (k 1) k n (k 1) 1 k n (k 1) n k n k k n (k 1) n! k!(n k)! n k n! (k 1)!(n (k 1))! n k n k 1 n k.

And by definition, since n k = 0 < 1 = n 0 for k < 0, we have in general that if k n 2

n k 1 n k,

or equivalently that if k n 2

n k n n2.

In the case that k > n 2 ,

k > n 2 k < n 2 n k < n n 2 n k < n + n 2 n k < n + n 2 n k < n 2

so that

n k = n n k n n2 = n n2.

That is for all integers n 1 and k

n k n n2 = n n2

as we needed to show. □

8. [00] What property of Pascal’s triangle is reflected in the “symmetry condition,” Eq. (6)?

The property of Pascal’s triangle that is reflected in the “symmetry condition,” Eq. (6), is the symmetry of the triangle itself. That is, each row, not counting zeros, is palindromic: values read the same left to right and vice versa.

9. [01] What is the value of n n? (Consider all integers n.)

Since n n = n 0 = 1 and n k = 0 for k < 0, we have

n n = 1if n 0 0otherwise.

10. [M25] If p is prime, show that:

a)
n p n p(modulo p).
b)
p k 0(modulo p), for 1 k p 1.
c)
p 1 k (1)k(modulo p), for 0 k p 1.
d)
p + 1 k 0(modulo p), for 2 k p 1.
e)
(É. Lucas, 1877.)
n k np kp n mod p k mod p(modulo p).
f)
If the p-ary number system representations of n and k are
n = arpr + + a1p + a0,
k = brpr + + b1p + b0,
thenn k ar br a1 b1 a0 b0 (modulo p).

The answers to exercise 10 follow below.

a)
We may prove the equivalence.

Proposition. n p n p (modp).

Proof. Let n and p be arbitrary integers such that n 1 and p prime. We must show that

n p n p(modp).

But given (e) with k = p,

n p np pp n mod p p mod p np 1 n mod p 0 np 1 n p(modp)

as we needed to show. □

b)
We may prove the equivalence.

Proposition. p k 0(modp) for 1 k p 1.

Proof. Let p and k be arbitrary integers such that p is prime and 1 k p 1. We must show that

p k 0(modp).

But given (e) with n = p, and since kp < 1,

p k pp kp p mod p k mod p 1 0 0 k 1 0 0(modp)

as we needed to show. □

c)
We may prove the equivalence.

Proposition. p1 k (1)k(modp) for 0 k p 1.

Proof. Let p and k be arbitrary integers such that p is prime and 0 k p 1. We must show that

p 1 k (1)k(modp).

If k = 0, then clearly

p 1 0 1 (1)k(modp).

Then, assuming

p 1 k (1)k(modp),

we must show that

p 1 k + 1 (1)k+1(modp).

But by the addition formula and (b),

p 1 k + 1 p k + 1 p 1 k p k + 1 (1)k 0 (1)k (1)k+1(modp)

as we needed to show. □

d)
We may prove the equivalence.

Proposition. p+1 k 0(modp) for 2 k p 1.

Proof. Let p and k be arbitrary integers such that p is prime and 2 k p 1. We must show that

p + 1 k 0(modp).

But by the addition formula Eq. (3) and (b),

p + 1 k p k + p k 1 0 + 0 0(modp)

as we needed to show. □

e)
We may prove the equivalence.

Proposition. n k np kp nmodp kmodp(modp).

Proof. Let n, k, and p be arbitrary integers such that p is prime. We must show that

n k np kp n mod p k mod p(modp).

Note that

n = n pp + (n mod p) 0 n mod p < p, k = k pp + (k mod p) 0 k mod p < p.

Also note from Eq. (7), that

sr s = rr 1 s 1,

with r = pnp and s = k implies

pnp s 0(modp)

and for arbitrary x that

(x + 1)npp (xp + 1)np(modp).

Then, for arbitrary x by the binomial theorem,

0knn kxk = (x + 1)n = (x + 1)npp+(nmodp) = (x + 1)npp(x + 1)nmodp (xp + 1)np(x + 1)nmodp(modp) = 0inp np i xip 0jnmodpn mod p j xj = 0ip+jnpp+(nmodp) np i n mod p j xip+j = 0kn np kp n mod p k mod pxk,

or equivalently, by equating coefficients

n k np kp n mod p k mod p(modp)

as we needed to show. □

f)
We may prove the equivalence.

Proposition. If n = 0iraipi and k = 0irbipi, then n k 0irai bi (modp).

Proof. Let n, k, and p be arbitrary integers such that n = 0iraipi and k = 0irbipi are the p-ary number representations of n and k with r coefficients ai, bi, respectively, 0 i r and 0 ai,bi p. We must show that

n k 0irai bi (modp).

If r = 0, then n = a0 and k = b0, and clearly,

n k a0 b0 0irai bi (modp).

Then, assuming for an arbitrary integer r 0 with n = 0iraipi and k = 0irbipi that

n k 0irai bi (modp),

we must show that

n k 0ir+1ai bi (modp)

for n = ar+1pr+1 + n = 0ir+1aipi and k = br+1pr+1 + k = 0ir+1bipi.

But given (e)

n k np kp n mod p k mod p 1 p 0ir+1aipi 1 p 0ir+1bipi 0ir+1aipi mod p 0ir+1bipi mod p 0ir+1aipi1 0ir+1bipi1 a0 b0 1ir+1aipi1 1ir+1bipi1 a0 b0 0irai+1pi 0irbi+1pi a0 b0 a0 b0 0irai+1pi 0irbi+1pi a0 b0 0irai+1 bi+1 a0 b0 1ir+1ai bi 0ir+1ai bi (modp)

as we needed to show. □

______________________________________________________________________________________________________________________________

É. Lucas, American J. Math. 1 (1878), 229–230; L. E. Dickson, Quart. J. Math. 33 (1902), 383–384; N. J. Fine, AMM 54 (1947), 589–592.

11. [M20] (E. Kummer, 1852.) Let p be prime. Show that if pn divides

a + b a

but pn+1 does not, then n is equal to the number of carries that occur when a is added to b in the p-ary number system. [Hint: See exercise 1.2.5-12.]

Proposition. If p is prime and pna+b a but pn+1 a+b a , then n is the number of carries that occur when a is added to b in the p-ary number system.

Proof. Let p, n, a, and b be arbitrary nonnegative integers such that p is prime,

pna + b a ,

and

pn+1 a + b a .

We must show that n is the number of carries that occur when a is added to b in the p-ary number system. That is, given representations a = 0krakpk, b = 0krbkpk, and a + b = c = 0krckpk, that n is zero for a + b < p and increases by one for every additional carry.

But

a + b a = c a = c! a!b!

and for μ from exercise 1.2.5-12,

pn c! a!b! pμ(c!) pμ(a!)pμ(b!) c! a!b! pμ(c!)μ(a!)μ(b!) c! a!b! n = μ(c!) μ(a!) μ(b!).

Then,

n = μ c! μ a! μ b! = c 0krck p 1 a 0krak p 1 b 0krbk p 1 = c 0krck a + 0krak b + 0krbk p 1 = 0krck + 0krak + 0krbk p 1 = 0krak + bk ck p 1 .

To see show that n is the number of carries, we construct an inductive argument. As our basis, we consider a + b < p, so that r = 0, a = a0 < p, b = b0 < p, and a + b = c = c0 < p. In this case, we have no carries, and n is given by

n = 0krak + bk ck p 1 = a0 + b0 c0 p 1 = 0,

as expected. Then, assuming n is the number of carries for arbitrary r and a + b = c, we must show that n = n + 1 for a + b = c given a single carry from digit κ 1 to κ as a result of the addition of ak1 + bk1 p, establishing the relation

ck = ck pif k = κ 1 ck + 1if k = κ ck otherwise.

But

n = 0krak + bk ck p 1 = 0kr κ1kκ ak + bk ck + 0kr k<κ1κ<k ak + bk ck p 1 = aκ1 + bκ1 cκ1 + aκ + bκ cκ + 0kr k<κ1κ<k ak + bk ck p 1 = aκ1 + bκ1 (cκ1 p) + aκ + bκ (cκ + 1) + 0kr k<κ1κ<k ak + bk ck p 1 = p 1 + aκ1 + bκ1 cκ1 + aκ + bκ cκ + 0kr k<κ1κ<k ak + bk ck p 1 = p 1 + 0kr κ1kκ ak + bk ck + 0kr k<κ1κ<k ak + bk ck p 1 = p 1 + 0krak + bk ck p 1 = 0krak + bk ck p 1 + p 1 p 1 = n + 1

as we needed to show. □

______________________________________________________________________________________________________________________________

Knuth and Wilf, Crelle 396 (1989), 212–219.

12. [M22] Are there any positive integers n for which all the nonzero entries in the nth row of Pascal’s triangle are odd? If so, find all such n.

We want to find all positive integers n such that if n k > 0, then n k 1(mod2). Let k be an arbitrary integer such that 0 k n, and, from Eq. (3), so that n k > 0. We want to find n such that

n k 1(mod2).

But, by exercise 1.2.6-10(f), given the binary representations n = 0irai2i and k = 0irbi2i,

n k 0irai bi 1(mod2)

if and only if each ai bi = 1. Since for each ai and bi, 0 ai,bi 1, of the four cases, we require bi ai; or equivalently, we require ai = 1 unless n = k = 0; or

n = 0ir2i = 2r+1 1.

Hence, all the nonzero entries in the nth row of Pascal’s triangle—those for which 0 k n—are odd if n = 2m 1 for some integer m 0. (This can be generalized to nondivisibility by a prime p if n = apm 1 for 1 a < p.)

13. [M13] Prove the summation formula, Eq. (10).

Proposition. 0knr+k k = r+n+1 n .

Proof. Let n and r be arbitrary integers such that n 0. We must show that

0knr + k k = r + n + 1 n .

If n = 0, from Eq. (4),

0knr + k k = 0k0r + k k = r + 0 0 = r 0 = 1 = r + 0 + 1 0 = r + n + 1 n .

Then, assuming

0knr + k k = r + n + 1 n ,

we must show that

0kn+1r + k k = r + n + 2 n + 1 .

But

0kn+1r + k k = r + n + 1 n + 1 + 0knr + k k = r + n + 1 n + 1 + r + n + 1 n = (r + n + 1)! (n + 1)!r! + (r + n + 1)! n!(r + 1)! = (r + 1)(r + n + 1)! (n + 1)!(r + 1)! + (n + 1)(r + n + 1)! (n + 1)!(r + 1)! = (r + 1)(r + n + 1)! + (n + 1)(r + n + 1)! (n + 1)!(r + 1)! = (r + n + 2)(r + n + 1)! (n + 1)!(r + 1)! = (r + n + 2)! (n + 1)!(r + 1)! = r + n + 2 n + 1

as we needed to show. □

14. [M21] Evaluate k=0nk4.

For an arbitrary integer k 0,

k4 = 0j44 jkj¯ from Eq. (45) = 0j44 jj!k j from Eq. (3) = 24k 4 + 36k 3 + 14k 2 + k 1.

Summing over k and from Eq. (11),

0knk4 = 0kn 24k 4 + 36k 3 + 14k 2 + k 1 = 24 0knk 4 + 36 0knk 3 + 14 0knk 2 + 0knk 1 = 24n + 1 5 + 36n + 1 4 + 14n + 1 3 + n + 1 2 = n5 5 + n4 2 + n3 3 n 30 = 1 30n(n + 1)(2n + 1)(3n2 + 3n 1) = n(n + 1)(n + 1 2)(3n2 + 3n 1) 15 .

15. [M15] Prove the binomial formula, Eq. (13).

Proposition. (x + y)r = 0krr kxkyrk.

Proof. Let x, y, and r be arbitrary integers such that r 0. We must show that

(x + y)r = 0krr kxkyrk.

If r = 0, then clearly

(x + y)r = (x + y)0 = 1 = 0 0x0y0 = 0krr kxkyrk.

Then, assuming

(x + y)r = 0krr kxkyrk,

we must show that

(x + y)r+1 = 0kr+1r + 1 k xkyr+1k.

But

(x + y)r+1 = (x + y)(x + y)r = (x + y) 0krr kxkyrk = x 0krr kxkyrk + y 0krr kxkyrk = 0krr kxk+1yrk + 0krr kxkyr+1k = 0k1r r k 1xkyr+1k + 0krr kxkyr+1k = 1kr+1 r k 1xkyr+1k + 0krr kxkyr+1k = 0kr+1 r k 1xkyr+1k + 0kr+1 r kxkyr+1k = 0kr+1r + 1 k xkyr+1k from Eq. (9)

as we needed to show. □

16. [M15] Given that n and k are positive integers, prove the symmetrical identity

(1)n n k 1 = (1)k k n 1.

Proposition. (1)n n k1 = (1)k k n1.

Proof. Let n and k be arbitrary positive integers. We must show that

(1)n n k 1 = (1)k k n 1.

But

(1)n n k 1 = (1)n(1)k1k 1 + n 1 k 1 from Eq. (17) = (1)n+k1n + k 2 k 1 = (1)k(1)n1n 1 + k 1 k 1 = (1)k(1)n1 n 1 + k 1 n 1 + k 1 (k 1) from Eq. (6) = (1)k(1)n1n 1 + k 1 n 1 = (1)k k n 1 from Eq. (17)

as we needed to show. □

17. [M18] Prove the Chu-Vandermonde formula (21) from Eq. (15), using the idea that (1 + x)r+s = (1 + x)r(1 + x)s.

Proposition. 0krr k s nk = r+s n .

Proof. Let r and s be arbitrary positive integers. We must show that

0krr k s n k = r + s n

from Eq. (15)

0krr kxk = (1 + x)r

and from the identity

(1 + x)r+s = (1 + x)r(1 + x)s.

But

0nr+sr + s n xn = (1 + x)r+s = (1 + x)r(1 + x)s = 0krr kxk 0kss kxk = 0krr kxk 0nks s n kxnk = 0nr+s 0krr k s n kxn.

Equating coefficients yields

r + s n = 0krr k s n k

as we needed to show. □

18. [M15] Prove Eq. (22) using Eqs. (21) and (6).

Proposition. k r m+k s n+k = r+s rm+n.

Proof. Let m, n, r, and s be arbitrary integers such that r 0. We must show that

k r m + k s n + k = r + s r m + n.

But

k r m + k s n + k = km r m + k m s n + k m = kr k s n + k m = kr k s k + n m = kr k s s k + m n from Eq. (6) = r + s r + s r + m n from Eq. (21) = r + s r m + n from Eq. (6)

as we needed to show. □

19. [M18] Prove Eq. (23) by induction.

Proposition. kr k s+k n (1)rk = s nr for integers n, r 0.

Proof. Let n, r, and s be arbitrary integers such that r 0. We must show that

kr k s + k n (1)rk = s n r.

If r = 0

kr k s + k n (1)rk = k0 k s + k n (1)k = 0 0 s + 0 n (1)0 = s n = s n r.

Then, assuming

kr k s + k n (1)rk = s n r,

we must show that

kr + 1 k s + k n (1)r+1k = s n r 1.

But

kr + 1 k s + k n (1)r+1k = k r k + r k 1 s + k n (1)r+1k = kr k s + k n (1)r+1k + k r k 1 s + k n (1)r+1k = kr k s + k n (1)rk + k+1 r k s + k + 1 n (1)rk = kr k s + k n (1)rk + kr k s + k + 1 n (1)rk = s n r + s + 1 n r = s + 1 n r s n r = s + 1 s + 1 (n r) s n r s n r = s + 1 s + 1 (n r) 1 s n r = n r s + 1 n + r s n r = n r s n + r + 1 s! (n r)!(s n + r)! = s! (n r 1)!(s n + r + 1)! = s n r 1

as we needed to show. □

20. [M20] Prove Eq. (24) by using Eqs. (21) and (19), then show that another use of Eq. (19) yields Eq. (25).

We may prove Eq. (24) using Eqs. (19) and (21).

Proposition. 0krrk m s kt(1)kt = rts rtm for nonnegative integers t, r, and m.

Proof. Let r, m, s, and t be arbitrary integers such that r,m,t 0. We must show that

0krr k m s k t(1)kt = r t s r t m.

But

0krr k m s k t(1)kt = 0kr(1)rkm (m + 1) r k m s k t(1)ktfrom Eq. (19) = 0kr(1)rmt (m + 1) r k m s k t = (1)rmt 0kr (m + 1) r k m s k t = (1)rmt tktrt (m + 1) r k t m s k = (1)rtm ks k (m + 1) r t m k = (1)rtms m 1 r t m from Eq. (21) = (1)rtmr t m r + t + s 1 r t m = r t s r t m from Eq. (17)

as we needed to show. □

We may also show that another use of Eq. (19) yields Eq. (25).

Proposition. 0krrk m s+k n = r+s+1 m+n+1 for nonnegative integers m, n, r, and s.

Proof. Let m, n, r, and s be arbtirary nonnegative integers. We must show that

0krr k m s + k n = r + s + 1 m + n + 1.

But

0krr k m s + k n = 0krr k m (1)s+kn (n + 1) s + k n from Eq. (19) = 0krr k m (n + 1) k (n s)(1)k(ns) = r (n s) + n + 1 r (n s) m from Eq. (24) = r + s + 1 r + s + 1 m n 1 = r + s + 1 m + n + 1 from Eq. (6)

as we needed to show. □

21. [M05] Both sides of Eq. (25) are polynomials in s; why isn’t that equation an identity in s?

According to the text on page 57, any polynomial 0kdaksk can be expressed as 0kdbks k for suitably chosen coefficients b0,b1,,bd.

And so, the left hand of Eq. (25) can be expressed as

0krr k m s + k n = 0knaksk;

that is, a polynomial of degree at most n for suitably chosen coefficients a0,a1,,an; and the right hand of Eq. (25) can be expressed as

r + s + 1 m + n + 1 = 0km+n+1aksk;

that is, a polynomial of degree at most m + n + 1 for suitably chosen coefficients a0,a1,,am+n+1.

Therefore, even though both sides of Eq. (25) are polynomials in s, since they do not agree at all m + n + 1 possible points, the equation does not serve as an identity in s.

22. [M20] Prove Eq. (26) for the special case s = n 1 r + nt.

Proposition. 0krtk k n1(rtk) nk r rtk = n1 n for integers n.

Proof. Let r, t, and n be arbtirary integers. We must show that

0kr tk k n 1 (r tk) n k r r tk = n 1 n .

We consider two cases, depending on whether k r tk or not.

Case 1. [k r tk] In the case that k r tk,

k r tk (r tk) k n (r tk) n k n 1 (r tk) < n k n 1 (r tk) n k = 0

which gives us that

0kr tk k n 1 (r tk) n k r r tk = 0 = n 1 n

in this case.

Case 2. [k > r tk] In the case that k > r tk, clearly

r tk < k r tk k = 0

which gives us that

0kr tk k n 1 (r tk) n k r r tk = 0 = n 1 n

in this case.

Therefore, in either case, we have that

0kr tk k n 1 (r tk) n k r r tk = 0 = n 1 n

as we needed to show. □

23. [M13] Assuming that Eq. (26) holds for (r,s,t,n) and (r,s t,t,n 1), prove it for (r,s + 1,t,n).

Proposition. If 0krtk k st(nk) nk r rtk = rstn n and 0krtk k st(nk) nk1 r rtk = rstn n1 , then 0krtk k st(nk)+1 nk r rtk = rstn+1 n .

Proof. Let r, s, t, and n be arbitrary integers such that

0kr tk k s t(n k) n k r r tk = r s tn n

and

0kr tk k s t(n k) n k 1 r r tk = r s tn n 1 .

We must show that

0kr tk k s t(n k) + 1 n k r r tk = r s tn + 1 n .

But

0kr tk k s t(n k) + 1 n k r r tk = 0kr tk k s t(n k) n k + s t(n k) n k 1 r r tk = 0kr tk k s t(n k) n k r r tk + 0kr tk k s t(n k) n k 1 r r tk = r s tn n + r s tn n 1 = r s tn + 1 n

as we needed to show. □

24. [M15] Explain why the results of the previous two exercises combine to give a proof of Eq. (26).

The results of the previous two exercises combine to give a proof of Eq. (26) as a proof by induction on n.

In the case that n < 0,

0kr tk k s t(n k) n k r r tk = 0 = r + s tn n ;

and in the case that n = 0,

0kr tk k s t(n k) n k r r tk = r 0 s 0 r r = 1 = r + s 0 = r + s tn n .

Otherwise, in the case that n > 0, we may construct a proof by induction on m 1 with s = n r + nt + m. If m = 1,

0kr tk k s t(n k) n k r r tk = 0kr tk k n r + nt + m t(n k) n k r r tk = 0kr tk k n 1 r + nt t(n k) n k r r tk = 0kr tk k n 1 (r tk) n k r r tk = n 1 n by exercise 22 = n + m n = r + n r + nt + m tn n = r + s tn n .

Then, assuming

0kr tk k s t(n k) n k r r tk = r s tn n

and

0kr tk k s t(n k) n k 1 r r tk = r s tn n 1 ,

we must show that

0kr tk k s t(n k) + 1 n k r r tk = r s tn + 1 n .

But, by exercise 24

0kr tk k s t(n k) + 1 n k r r tk = r s tn + 1 n

and hence the result.

25. [HM30] Let the polynomial An(x,t) be defined as in Eq. (30). Let z = xt+1 xt. Prove that kAk(r,t)zk = xr, provided z is small enough. [Note: If t = 0, this result is essentially the binomial theorm, and this equation is an important generalization of the binomial theorem. The binomial theorem (15) may be assumed in the proof.] Hint: Start with the identity

j(1)jk j r jt k r r jt = δk0.

Proposition. kAk(r,t)zk = xr for z = xt+1 xt sufficiently small.

Proof. Let An(x,t) be the nth degree polynomial in x that satisfies

An(x,t) = x nt n x x nt

for xnt; and z = xt+1 xt sufficiently small. We must show that

jAj(r,t)zj = xr.

We may first prove that the sum converges by using the ratio test; that is, that

lim kAk+1(r,t)zk+1 Ak(r,t)zk < 1.

But if z is sufficiently small, z 1t, or equivalently, tz < 1, then

1 > tz = lim k(r kt) (k + 1) z = lim k 1jk(r kt)(r (k + 1)t)(r kt + 1 j) (r (k + 1)t)(k + 1)(r kt + 1 j) z lim k 1jk(r kt)(r (k + 1)t k)(r (k + 1)t + 1 j) (r (k + 1)t)(k + 1)(r kt + 1 j) z = lim k(r kt)z(r (k + 1)t k) 1jk(r (k + 1)t + 1 j) (r (k + 1)t)(k + 1) 1jk(r kt + 1 j) = lim k(r kt)zr(k+1)tk k+1 1jkr(k+1)t+1j j (r (k + 1)t) 1jkrkt+1j j = lim k(r kt)z 1jk+1r(k+1)t+1j j (r (k + 1)t) 1jkrkt+1j j = lim kr(k+1)t k+1 (r kt)z rkt k (r (k + 1)t) = lim kr(k+1)t k+1 r r(k+1)tz rkt k r rkt = lim kAk+1(r,t)z Ak(r,t) = lim kAk+1(r,t)zk+1 Ak(r,t)zk

and hence the proof of convergence.

Then, given the identity

j(1)jk j r jt k r r jt = δk0,

and letting x = 1(1 + w) so that z = w(1 + w)t+1 = xt+1 xt, we have that

1 = δ00 = kδk0wk = k j(1)jk j r jt k r r jtwk = j(1)j r r jt kk j r jt k wk = j(1)j r r jt kr jt j r jt j k j wk from Eq. (2) = j(1)jr jt j r r jt kr jt j k j wk = j(1)jA j(r,t) kr jt j k j wk = j(1)jA j(r,t) kr jt j k j wkjwj = j(1)jA j(r,t)(1 + w)rjtjwj = j(1)jA j(r,t)(1x)rjtj(1x 1)j = jAj(r,t)(1)j(1x)rjtj(1x 1)j = jAj(r,t)(1)j(1x 1)j(1x)rjtj = jAj(r,t)(1)j(1x 1)j(1x)jtj(1x)r = jAj(r,t)((1x 1))j((1x)t1)j(1x)r = jAj(r,t)((1 1x)xt+1)j(1x)r = jAj(r,t)(xt+1 xt)j(1x)r = jAj(r,t)zj(1x)r;

or equivalently, that

jAj(r,t)zj = xr

as we needed to show. □

______________________________________________________________________________________________________________________________

H. W. Gould, AMM 63 (1956), 84–91.

26. [HM25] Using the assumptions of the previous exercise, prove that

kr tk k zk = xr+1 (t + 1)x t.

Proposition. krtk k zk = xr+1 (t+1)xt.

Proof. Let An(x,t) be the nth degree polynomial in x from exercise 25 that satisfies

An(x,t) = x nt n x x nt

for xnt; and z = xt+1 xt sufficiently small so that z 1t. We must show that

kr tk k zk = xr+1 (t + 1)x t.

From exercise 25, we have that kAk(r,t)zk = xr, or equivalently that

1 = kAk(r,t)zkxr = kAk(r,t)(xt+1 xt)kxr = kAk(r,t)xtkr(x 1)k;

we have by definition that

1 = dz dz = d dz(xt+1 xt) = ((t + 1)xt txt1)dx dz = xt1((t + 1)x t)dx dz

or equivalently that

dx dz = x xt((t + 1)x t);

and we also have that d dz kAk(r,t)zk = kkAk(r,t)zk1 = d(xr) dz , or equivalently that

kkAk(r,t)zk = zd(xr) dz = (xt+1 xt)rxr1dx dz = (xt+1 xt)rxr1 x xt((t + 1)x t) = rxr1( x2 (t + 1)x t x (t + 1)x t) = rxr x 1 (t + 1)x t.

Finally, diffirentiating the first equality yields

d dx1 = 0 = d dx kAk(r,t)xtkr(x 1)k = kAk(r,t) (x 1)k(tk r)(xtkr1) + xtkrk(x 1)k1 = kAk(r,t) (tk r)(xr1) + xrk(x 1)1 (x 1)kxtk = kAk(r,t) (tk r)(xr1) + xrk(x 1)1 zk = k(tk r)(xr1)A k(r,t)zk + kxrk(x 1)1A k(r,t)zk = k(tk r)(xr1)r kt k r r ktzk + kxrk(x 1)1A k(r,t)zk = k(r)(xr1)r kt k zk + kxrk(x 1)1A k(r,t)zk = rx1 kr kt k zk + (x 1)1 kkAk(r,t)zk = rx1 kr kt k zk + (x 1)1rxr x 1 (t + 1)x t = rx1 kr kt k zk + rxr (t + 1)x t

if and only if

kr kt k zk = x r rxr (t + 1)x t = xr+1 (t + 1)x t

as we needed to show. □

27. [HM21] Solve Example 4 in the text by using the result of exercise 25, and prove Eq. (26) from the preceding two exercises. [Hint: See exercise 17.]

We may solve Example 4 from the text using the result of exercise 25.

Proposition. kAk(r,t)Ank(s,t) = An(r + s,t) for nonnegative integers n.

Proof. Let An(x,t) be the nth degree polynomial in x from exercise 25 that satisfies

An(x,t) = x nt n x x nt

for xnt; and z = xt+1 xt sufficiently small so that z 1t. We must show that

kAk(r,t)Ank(s,t) = An(r + s,t).

From exercise 25, we have that nAn(r + s,t)zn = xr+s. And so,

n kAk(r,t)Ank(s,t)zn = n k j j=nk Ak(r,t)Aj(s,t)zn = k j j=nk Ak(r,t)Aj(s,t)zj+k = kAk(r,t)zk jAj(s,t)zj = xrxs = xr+s = nAn(r + s,t)zn = xr+s.

Equating coefficients yields

kAk(r,t)Ank(s,t) = An(r + s,t)

as we needed to show. □

We may also prove Eq. (26) from the preceding two exercises.

Proposition. k0rtk k st(nk) nk r rtk = r+stn n .

Proof. Let n be an arbitrary integer. We must show that

k0r tk k s t(n k) n k r r tk = r + s tn n .

From exercise 25, we have that k0Ak(r,t)zk = xr and from exercise 26, we have that jstj j zj = xs+1 (t+1)xt. Multiplying both equations yields

xr xs+1 (t + 1)x t = xr+s+1 (t + 1)x t = k0Ak(r,t)zk js tj j zj = k0Ak(r,t)zk n j=nk s t(n k) n k znk = n k0Ak(r,t)s t(n k) n k zn = n k0r kt k r r kt s t(n k) n k zn; = n k0r kt k s t(n k) n k r r ktzn;

and again, from exercise 26,

xr+s+1 (t + 1)x t = nr + s tn n zn,

which gives us the equality

n k0r kt k s t(n k) n k r r ktzn = nr + s tn n zn.

Finally, equating coefficients yields

k0r kt k s t(n k) n k r r kt = r + s tn n ,

and hence the result. □

28. [M25] Prove that

kr + tk k s tk n k = k0r + s k n k tk,

if n is a nonnegative integer.

Proposition. kr+tk k stk nk = k0r+sk nk tk for n a nonnegative integer.

Proof. Let n be an arbitrary nonnegative integer. We must show that

kr + tk k s tk n k = k0r + s k n k tk.

If n = 0,

kr + tk k s tk n k = kr + tk k s tk k = 0 = k0r + s k k = k0r + s k k tk.

Then, assuming

kr + tk k s tk n k = k0r + s k n k tk

we must show that

kr + tk k s tk n + 1 k = k0 r + s k n + 1 ktk.

But from Eq. (26),

kr + tk k s tk n + 1 k = kr + tk k s tk n + 1 k r + tk r + tk = kr + tk k s tk n + 1 k r r + tk + kr + tk k s tk n + 1 k tk r + tk = kr (t)k k (s tn) (t)(n k) n + 1 k r r (t)k + kr + tk k s tk n + 1 k tk r + tk = r + (s tn) (t)n n + 1 + kr + tk k s tk n + 1 k tk r + tk = r + s n + 1 + t k k r + tk r + tk k s tk n + 1 k = r + s n + 1 + t kr + tk 1 k 1 s tk n + 1 k = r + s n + 1 + t kr + t(k + 1) 1 k + 1 1 s t(k + 1) n + 1 (k + 1) = r + s n + 1 + t kr + t 1 + tk k s t tk) n k = r + s n + 1 + t k0r + t 1 + s t k n k tk = r + s n + 1 + t k0r + s k 1 n k tk = r + s n + 1 + k0 r + s (k + 1) n + 1 (k + 1)tk+1 = r + s 0 n + 1 0t0 + k1 r + s k n + 1 ktk = k0 r + s k n + 1 ktk

as we needed to show. □

29. [M20] Show that Eq. (34) is just a special case of the general identity proved in exercise 1.2.3-33.

Eq. (34) for r 0 is

kr k(1)rk 0jrbjkj = r!b r,

while the general identity proved in exercise 1.2.3-33 is

1kr kj 1ir ik (k i) = 0 if 0 j < r 1 1 if j = r 1 1krkif j = r.

Thus,

kr k(1)rk 0jrbjkj = 0krr k(1)rk 0jrbjkj = 0jrbj 0krr k(1)rkkj = 0jrbj 0kr r! k!(r k)!(1)rkkj = r! 0jrbj 0kr kj (1)rkk!(r k)! = r! 0jrbj 0kr kj 1irk(1) 1iki 1irki = r! 0jrbj 0kr kj 1iki 1irk(i) = r! 0jrbj 0kr kj 0ik1(k i) k+1ir(k i) = r! 0jrbj 0kr kj 0ir ik (k i) = r! 1jr1bj+1 1kr kj 1ir ik (k i) = r!br1+1(1) = r!br

and hence the result.

30. [M24] Show that there is a better way to solve Example 3 than the way used in the text, by manipulating the sum so that Eq. (26) applies.

We wish to evaluate the sum from Example 3

k n + k m + 2k 2k k (1)k k + 1

for positive integers m and n, using Eq. (26)

k01 + 2k k m 1 2k n m k 1 1 + 2k = m n m.

But

k n + k m + 2k 2k k (1)k k + 1 = k n + k m + 2k 2k k (1)k k + 1 2k + 1 2k + 1 = k n + k m + 2k 2k + 1 k + 1 2k k (1)k 2k + 1 = k0 n + k m + 2k 2k + 1 k + 1 (1)k 2k + 1 from Eq. (7) = k0 n + k m + 2k 2k + 1 k (1)k 2k + 1 from Eq. (6) = k0(1)n+km2k (m + 2k + 1) n + k m 2k 2k + 1 k (1)k 2k + 1 from Eq. (19) = k0m 2k 1 n m k 2k + 1 k (1)nmk(1)k 2k + 1 = k0m 2k 1 n m k 2k + 1 k (1)nm 2k + 1 = k0m 2k 1 n m k 2k + 1 k (1)nm 2k + 1 = k01 + 2k k m 1 2k n m k (1)nm 1 + 2k = (1)nm m n m from Eq. (26) = (1)nmn m n + 1 1 n m = n 1 n m from Eq. (17) = n 1 n 1 n + m from Eq. (6) = n 1 m 1

and hence the result.

31. [M20] Evaluate

km r + s k n + r s n k r + k m + n

in terms of r, s, m, and n, given that m and n are integers. Begin by replacing

r + k m + nby j r m + n j k j .

We have

km r + s k n + r s n k r + k m + n = km r + s k n + r s n k j r m + n j k j = j km r + s k k j n + r s n k r m + n j = j km r + s j m r + s j k j n + r s n k r m + n j from Eq. (20) = j km r + s j m r + s j m r + s k n + r s n k r m + n j from Eq. (6) = j km r + s j m r + s j m r + s k n + r s r s + k r m + n j from Eq. (6) = jm r + s j r m + n j k m r + s j m (k + r s) n + r s k + r s = jm r + s j r m + n j kn + r s k m r + s j m k = jm r + s j r m + n j n + m j m from Eq. (21) = jm r + s j r m r m n j from Eq. (20) = r m jm r + s j r m n j = r m s n. from Eq. (21)

______________________________________________________________________________________________________________________________

J. F. Plaff, Nova Acta Acad. Scient. Petr. 11 (1797), 38–57.

32. [M20] Show that kn k xk = xn¯, where xn¯ is the rising factorial power defined in Eq. 1.2.5-(19).

Proposition. kn k xk = xn¯.

Proof. Let xn¯ be the rising factorial power defined as

xn¯ = 0kn1(x + k).

We must show that

kn kxk = xn¯.

But

kn kxk = kn k (1)k(x)k = kn k (1)k(x)k = kn k (1)nn(1)k(x)k = kn k (1)n(1)n(1)k(x)k = (1)n kn k (1)nk(x)k = (1)n(x)n̲ from Eq. (44) = xn¯ from Eq. 1.2.5-(20)

as we needed to show. □

33. [M20] (A. Vandermonde, 1772.) Show that the binomial formula is valid also when it involves factorial powers instead of the ordinary powers. In order words, prove that

(x + y)n̲ = kn kxk̲ynk̲;(x + y)n¯ = kn kxk¯yn k¯.

We may prove the formula for factorial falling.

Proposition. (x + y)n̲ = kn k xk̲ynk̲.

Proof. Let n be an arbitrary nonnegative integer. We must show that

(x + y)n̲ = kn kxk̲ynk̲.

If n = 0,

(x + y)0̲ = 1 = 0 0x0̲y0̲ = k0 kxk̲y0k̲.

Then, assuming

(x + y)n̲ = kn kxk̲ynk̲

we must show that

(x + y)n+1̲ = kn + 1 k xk̲yn+1k̲.

But

(x + y)n+1̲ = (x + y n)(x + y)n̲ = (x + y n) kn kxk̲ynk̲ = kn kxk̲ynk̲((x k) + (y (n k))) = kn kxk+1̲ynk̲ + kn kxk̲yn+1k̲ = k n k 1xk̲yn+1k̲ + kn kxk̲yn+1k̲ = k n k 1 + n kxk̲yn+1k̲ = kn + 1 k xk̲yn+1k̲ from Eq. (9)

as we needed to show. □

We may also prove the formula for factorial rising.

Proposition. (x + y)n¯ = kn k xk¯yn k¯.

Proof. Let n be an arbitrary nonnegative integer. We must show that

(x + y)n¯ = kn kxk¯yn k¯.

If n = 0,

(x + y)0¯ = 1 = 0 0x0¯y0¯ = k0 kxk¯y0 k¯.

Then, assuming

(x + y)n¯ = kn kxk¯yn k¯

we must show that

(x + y)n + 1¯ = kn + 1 k xk¯yn + 1 k¯.

But

(x + y)n + 1¯ = (x + y + n)(x + y)n¯ = (x + y + n) kn kxk¯yn k¯ = kn kxk¯yn k¯((x + k) + (y + (n k))) = kn kxk + 1¯yn k¯ + kn kxk¯yn + 1 k¯ = k n k 1xk¯yn + 1 k¯ + kn kxk¯yn + 1 k¯ = k n k 1 + n kxk¯yn + 1 k¯ = kn + 1 k xk¯yn + 1 k¯ from Eq. (9)

as we needed to show. □

34. [M23] (Torelli’s sum.) In the light of the previous exercise, show that Abel’s generalization, Eq. (16), of the binomial formula is true also for rising powers:

(x + y)n¯ = kn kx(x kz + 1)k 1¯(y + kz)n k¯.

Proposition. (x + y)n¯ = kn k x(x kz + 1)k 1¯(y + kz)n k¯.

Proof. Let n be an arbitrary nonnegative integer and x an arbitrary nonzero real number. We must show that

(x + y)n¯ = kn kx(x kz + 1)k 1¯(y + kz)n k¯.

Given the general identity for arbitrary a

an¯ = Γ(a + n) Γ(a) = (a + n)!a (a + n)a! = (a + n 1)! (a 1)! = (a + n 1)! (a + n 1 n)! = n!(a + n 1)! n!(a + n 1 n)! = n!(a + n 1)! n!(a + n 1 n)! = n!a + n 1 n ,

we have that

(x + y)n¯ = n!x + y + n 1 n = n! kx (z 1)k k y + nz 1 (z 1)(n k) n k x x (z 1)k from Eq. (26) = n! kx k k x (z 1)k x (z 1)k k y + nz 1 (z 1)(n k) n k = n! kx k x (z 1)k 1 k 1 y + nz 1 (z 1)(n k) n k from Eq. (7) = n! kx k x (z 1)k 1 k 1 y + kz + n k 1 n k = k n! k!(n k)!(k 1)!(n k)!xx k(z 1) 1 k 1 y + kz + n k 1 n k = kn kx(k 1)!x kz + 1 + k 1 1 k 1 (n k)!y + kz + n k 1 n k = kn kx(x kz + 1)k 1¯(y + kz)n k¯

as we needed to show. □

______________________________________________________________________________________________________________________________

A. Vandermonde, Mém. Acad. Roy. Sci. (Paris, 1772), part 1, 492; C. Kramp, Élémens d’Arithmétique Universelle (Cologne: 1808), 359; G. Torelli, Giornale di Mat. Battaglini 33 (1895), 179–182; H. A. Rothe, Formulæde Serierum Reversione (Leipzig: 1793), 18.

35. [M23] Prove the addition formulas (46) for Stirling numbers directly from the definitions, Eqs. (44) and (45).

We may prove the addition formula for Stirling numbers of the first kind.

Proposition. n+1 m = n n m + n m1.

Proof. Let m and n be arbitrary nonnegative integers. We must show that

n + 1 m = n n m + n m 1.

But from Eq. (44),

k(1)n+1kn + 1 k xk = xn+1̲ = (x n)xn̲ = nxn̲ + xxn̲ = n k(1)nkn kxk + x k(1)nkn kxk = n k(1)nkn kxk + x k(1)n(k1) n k 1xk1 = k(1)n+1knn kxk + k(1)n+1k n k 1xk = k(1)n+1k nn k + n k 1xk

and hence the result equating coefficients. □

We may also prove the addition formula for Stirling numbers of the second kind.

Proposition. n+1 m = m n m + n m1.

Proof. Let m and n be arbitrary nonnegative integers. We must show that

n + 1 m = m n m + n m 1.

But from Eq. (45),

kn + 1 k xk̲ = xn+1 = xxn = x kn kxk̲ = kn kxxk̲ = kn k xxk̲ + kxk̲ kxk̲ = kn k (x k)xk̲ + kxk̲ = kn k xk+1̲ + kxk̲ = kn kkxk̲ + kn kxk+1̲ = kkn kxk̲ + k n k 1xk̲ = k kn k + n k 1xk̲

and hence the result equating coefficients. □

36. [M10] What is the sum kn k of the numbers in each row of Pascal’s triangle? What is the sum of these numbers with alternating signs, kn k (1)k?

Assuming n a nonnegative integer, from Eq. (13),

kn k = kn k 1k1nk = (1 + 1)n = 2n,

and

kn k (1)k = kn k (1)k1nk = (1 + 1)n = 0n = δn0.

37. [M10] From the answers to the preceding exercise, deduce the value of the sum of every other entry in a row, n 0 + n 2 + n 4 + .

Again assuming n a nonnegative integer, from the preceding exercise,

k evenn k = kn k k oddn k = kn k + k evenn k k oddn k 2 = kn k + k evenn k (1)k +k oddn k (1)k 2 = kn k + kn k (1)k 2 = 2n + δn0 2 = 1 if n = 0 2n1if n > 0.

38. [HM30] (C. Ramus, 1834.) Generalizing the result of the preceding exercise, show that we have the following formula, given that 0 k < m:

n k + n m + k + n 2m + k + = 1 m 0j<m 2cos jπ m n cos j(n 2k)π m .

For example,

n 1 + n 4 + n 7 + = 1 3 2n + 2cos (n 2)π 3 .

[Hint: Find the right combinations of these coefficients multiplied by mth roots of unity.] This identity is particularly remarkable when m n.

Proposition. j0 n jm+k = 1 m 0j<m 2cos jπ m n cos j(n2k)π m .

Proof. Let k and m be arbitrary integers such that 0 k < m. We must show that

j0 n jm + k = 1 m 0j<m 2cos jπ m n cos j(n 2k)π m .

Given ω = e2πim and the sum of the geometric progression for t restricted such that t mod m = k,

0j<mωj(tk) = 0j<m ωtk j = 0j<m e2πi(tk)m j = 0j<m (1)2(tk)m j = 0j<m 1(tk)m j = [t k 0(modm)] 0j<m1j = [t k 0(modm)]m

we have for the real part that

j0 n jm + k = tmodm=kn t = tk0(modm)n t = tn t [t k 0(modm)] = tn t 1 m 0j<mωj(tk) = 1 m 0j<mωjk tn t ωjt = 1 m 0j<mωjk 1 + ωj n = 1 m 0j<mωjk ωj + 1n = 1 m 0j<mωjk ωj2ωj2 + ωj2ωj2 n = 1 m 0j<mωjkωjn2 ωj2 + ωj2 n = 1 m 0j<mωj(n2k) ωj2 + ωj2 n = 1 m 0j<me2πij(n2k)m e2πijm2 + e2πijm2 n = 1 m 0j<meij(n2k)π m eijπ m + eijπ m n = 1 m 0j<m cos j(n 2k)π m 2cos jπ m n = 1 m 0j<m 2cos jπ m n cos j(n 2k)π m

as we needed to show. □

______________________________________________________________________________________________________________________________

C. Ramus, Crelle 11 (1834), 353–355; CMath, exercises 5.75 and 6.57.

39. [M10] What is the sum kn k of the numbers in each row of Stirling’s first triangle? What is the sum of these numbers with alternating signs? (See exercise 36.)

Assuming n a nonnegative integer, from exercise 32 we have that

kn k = kn k 1k = 1n¯ = 0jn1(1 + j) from Eq. 1.2.5-(19) = 1jnj = n!

and from Eq. (44) we have that

kn k (1)k = kn k (1)k = kn k (1)nkn = k(1)nkn k (1)n = k(1)nkn k (1)n = k(1)nkn k 1k(1)n = 1n̲(1)n = 0jn1(1 j)(1)n from Eq. 1.2.5-(18) = 1 if n = 0 1 if n = 1 0 otherwise = δn0 δn1.

40. [HM17] The beta function B(x,y) is defined for positive real numbers x, y by the formula B(x,y) =01tx1(1 t)y1dt.

a)
Show that B(x,1) = B(1,x) = 1x.
b)
Show that B(x + 1,y) + B(x,y + 1) = B(x,y).
c)
Show that B(x,y) = ((x + y)y)B(x,y + 1).

Let x and y be arbitrary positive real numbers and define the beta function B(x,y) as

B(x,y) =01tx1(1 t)y1dt.
a)
We may show the first identity.

Proposition. B(x,1) = B(1,x) = 1x.

Proof. We must show that

B(x,1) = B(1,x) = 1x. (68)

But by definition, both

B(x,1) =01tx1(1 t)11dt = 10(1 t)x1(1 (1 t))11dt =01t11(1 t)x1dt = B(1,x)

and

B(x,1) =01tx1(1 t)11dt =01tx1dt = tx x 01 = 1 x 0 x = 1 x

and hence the result. □

b)
We may show the second identity.

Proposition. B(x + 1,y) + B(x,y + 1) = B(x,y).

Proof. We must show that

B(x + 1,y) + B(x,y + 1) = B(x,y). (71)

But

B(x + 1,y) + B(x,y + 1) =01tx+11(1 t)y1dt +01tx1(1 t)y+11dt =01 tx+11(1 t)y1 + tx1(1 t)y+11 dt =01 ttx1(1 t)y1 + (1 t)tx1(1 t)y1 dt =01(t + 1 t)tx1(1 t)y1dt =01tx1(1 t)y1dt = B(x,y)

and hence the result. □

c)
We may show the third identity.

Proposition. B(x,y) = ((x + y)y)B(x,y + 1).

Proof. We must show that

B(x,y) = ((x + y)y)B(x,y + 1). (73)

But from integration by parts

01txy(1 t)y1dt = tx(1 t)y 01 01xtx1(1 t)ydt

which gives us that

B(x + 1,y) =01tx(1 t)y1dt = tx(1 t)y y 01 + x y01tx1(1 t)ydt = tx(1 t)y y 01 + x yB(x,y + 1) = 1x(1 1)y y + 0x(1 0)y y + x yB(x,y + 1) = x yB(x,y + 1).

Then, from (b)

B(x,y) = B(x + 1,y) + B(x,y + 1) = x yB(x,y + 1) + B(x,y + 1) = x + y y B(x,y + 1)

and hence the result. □

41. [HM22] We proved a relation between the gamma function and the beta function in exercise 1.2.5-19, by showing that Γm(x) = mxB(x,m + 1), if m is a positive integer.

a)
Prove that
B(x,y) = Γm(y)mx Γm(x + y)B(x,y + m + 1).
b)
Show that
B(x,y) = Γ(x)Γ(y) Γ(x + y) .

Define the gamma function for positive integers m as

Γm(x) = mxm! 0jm(x + j),

so that from exercise 1.2.5-19

Γm(x) = mxB(x,m + 1).
a)
We may prove the first identity.

Proposition. B(x,y) = Γm(y)mx Γm(x+y) B(x,y + m + 1).

Proof. Let m be a positive integer. We must show that

B(x,y) = Γm(y)mx Γm(x + y)B(x,y + m + 1).

As an initial corollary, we will first show for positive integers k that

B(x,y) = 0j<kx + y + j y + j B(x,y + k).

If k = 1 we have from exercise 40 (c) that

B(x,y) = x + y y B(x,y + 1) = 0j<kx + y + j y + j B(x,y + k).

Then, assuming

B(x,y) = 0j<kx + y + j y + j B(x,y + k)

we must show that

B(x,y) = 0j<k+1x + y + j y + j B(x,y + k + 1).

But again from exercise 40 (c)

B(x,y) = 0j<kx + y + j y + j B(x,y + k) = 0j<kx + y + j y + j x + y + k y + k B(x,y + k + 1) = 0j<k+1x + y + j y + j B(x,y + k + 1)

and hence the interim result. Then finally,

B(x,y) = 0j<m+1x + y + j y + j B(x,y + m + 1) = 0jmx + y + j y + j B(x,y + m + 1) = 0jm(x + y + j) 0jm(y + j) B(x,y + m + 1) = mx+ym! 0jm(x + y + j) mx+ym! 0jm(y + j) B(x,y + m + 1) = mym! 0jm(y + j) mx+ym! 0jm(x + y + j)mxB(x,y + m + 1) = Γm(y)mx Γm(x + y)B(x,y + m + 1)

as we needed to show. □

b)
We may show the second identity.

Proposition. B(x,y) = Γ(x)Γ(y) Γ(x+y) .

Proof. Let m be a positive integer. We must show that

B(x,y) = Γ(x)Γ(y) Γ(x + y) .

It is sufficient to show that

lim mmxB(x,y + m + 1) = Γ(x).

Note that B is monotonically decreasing for positive x and y. That is, if (x,y) (x,y + 1), then B(x,y) B(x,y + 1), since from exercise 40

x > 0 y > 0 x y 0 x y + 1 1 x + y y 1 x + y y B(x,y + 1) B(x,y + 1) B(x,y) B(x,y + 1).

Then, since B is monotonically decreasing and from exercise 1.2.5-19,

y + m + 1 y + m + 1 < n + m + 2 B(x,y + m + 2) < B(x,y + m + 1) B(x,y + m + 1) Γy+m+1(x) (y + m + 1)x < B(x,y + m + 1) Γy+m(x) (y + m)x Γy+m+1(x) mx(1 + (y + 1)m)x < B(x,y + m + 1) Γy+m(x) mx(1 + ym)x m y + m + 1xΓ y+m+1(x) < mxB(x,y + m + 1) m y + mxΓ y+m(x) lim m m y + m + 1xΓ y+m+1(x) < lim mmxB(x,y + m + 1) lim m m y + mxΓ y+m(x) lim mΓy+m+1(x) < lim mmxB(x,y + m + 1) lim mΓy+m(x) lim mΓm(x) < lim mmxB(x,y + m + 1) lim mΓm(x) Γ(x) < lim mmxB(x,y + m + 1) Γ(x) lim mmxB(x,y + m + 1) = Γ(x).

And so from (a),

B(x,y) = lim m Γm(y)mx Γm(x + y)B(x,y + m + 1) = lim mmxB(x,y + m + 1)Γm(y) Γm(x + y) = Γ(x)Γ(y) Γ(x + y)

as we needed to show. □

42. [HM10] Express the binomial coefficient r k in terms of the beta function defined above. (This gives us a way to extend the definition to all real values of k.)

From exercise 41 (b) we have

r k = r! k!(r k)! = (r + 2)!(k + 1)(r k + 1) (r + 1)(r + 2)(k + 1)!(r k + 1)! = Γ(r + 2) (r + 1)Γ(k + 1)Γ(r k + 1) = Γ(k + 1 + r k + 1) (r + 1)Γ(k + 1)Γ(r k + 1) = 1 (r + 1)B(k + 1,r k + 1).

______________________________________________________________________________________________________________________________

L. Ramshaw, Inf. Proc. Letters 6 (1977), 223–226.

43. [HM20] Show that B(12,12) = π. (From exercise 41 we may now conclude that Γ(12) = π.)

Proposition. B(12,12) = π.

Proof. Define the beta function B(x,y) as

B(x,y) =01tx1(1 t)y1dt.

We must show that

B(12,12) = π.

But for u = t12, du = 1 2t12 dt,

B(12,12) =01t121(1 t)121dt =01 1 t12(1 t)12dt =01 2t12 t12(1 u2)12du = 201 1 (1 u2)12du = 2 arcsin u01 = 2(π2 0) = π

as we needed to show. □

44. [HM20] Using the generalized binomial coefficient suggested in exercise 42, show that

r 12 = 22r+12r r π.

Proposition. r 12 = 22r+12r r π.

Proof. As a corollary, we will prove Gauss’s multiplication formula. That is, that

Γ(nz) = (2π)(1n)2nnz12 0kn1Γ z + k n.

By Stirling’s formula as m , we have

Γ z + k n = z + k n 1Γ z + k n 1 = lim mmz+kn1m! 0jm1 z + k n + j = lim mmz+kn12πm m e m 0jm1 z + k n + j = lim mmz+kn122π mn e m 0jm1 nz + k + jn,

and

0kn1Γ z + k n = lim mmnzn2m 0kn1kn 2πn mn e mn 0kn1 0jm1 nz + k + jn = lim mmnzn2m 0kn1kn 2πn mn e mn 0jmn1 nz + j = lim mmnz12 2πn mn e mn 0jmn1 nz + j = lim m(mn)nz12 2πn (mn)n e (mn)n 0j(mn)n1 nz + j = lim mmnz12n12nz 2πn m e m 0jm1 nz + j = lim mmnz1n12nz 2πn12πm m e m 0jm1 nz + j = lim mmnz1n12nz 2πn1m! 0jm1 nz + j = (2π)(n1)2n12nz lim mmnz1m! 0jm1 nz + j = (2π)(n1)2n12nz(nz 1)Γ(nz 1) = (2π)(n1)2n12nzΓ(nz),

and hence the result

Γ(nz) = (2π)(1n)2nnz12 0kn1Γ z + k n.

For the proof, we must show that

r 12 = 22r+12r r π.

But from exercise 42 and since Γ(32) = Γ(12)2 = π2,

r 12 = 1 (r + 1)B(12 + 1,r 12 + 1) = 1 (r + 1)B(32,r + 12) = Γ(32 + r + 12) (r + 1)Γ(32)Γ(r + 12) = Γ(r + 2) (r + 1)Γ(32)Γ(r + 12) = 2Γ(r + 2) (r + 1)πΓ(r + 12)

and

2r r = 1 (2r + 1)B(r + 1,2r r + 1) = 1 (2r + 1)B(r + 1,r + 1) = Γ(r + 1 + r + 1) (2r + 1)Γ(r + 1)Γ(r + 1) = Γ(2r + 2) (2r + 1)Γ(r + 1)Γ(r + 1).

Multiplying both equalities yields

r 12 2r r = 2Γ(r + 2) (r + 1)πΓ(r + 12) Γ(2r + 2) (2r + 1)Γ(r + 1)Γ(r + 1) = 2Γ(r + 2)Γ(2r + 2) (r + 1)πΓ(r + 12)(2r + 1)Γ(r + 1)Γ(r + 1) = 2Γ(r + 2)(2r + 1)Γ(2r + 1) (r + 1)πΓ(r + 12)(2r + 1)Γ(r + 1)Γ(r + 1) = 2Γ(r + 2)Γ(2r + 1) (r + 1)πΓ(r + 12)Γ(r + 1)Γ(r + 1) = 2(r + 1)Γ(r + 1)Γ(2r + 1) (r + 1)πΓ(r + 12)Γ(r + 1)Γ(r + 1) = 2Γ(2r + 1) πΓ(r + 12)Γ(r + 1)

if and only if

r 12 = 2Γ(2r + 1)πΓ(r + 12)Γ(r + 1)2r r .

That is, it is sufficient to show that

Γ(2r + 1) Γ(r + 1)Γ(r + 12) = 22r π.

But, by Guass’s multiplication formula,

Γ(2r + 1) Γ(r + 1)Γ(r + 12) = 2r Γ(r + 1)Γ(r + 12)Γ(2r) = 2r Γ(r + 1)Γ(r + 12)(2π)(12)222r12 0k21Γ r + k 2 = 2r Γ(r + 1)Γ(r + 12)(2π)1222r12Γ(r)Γ r + 1 2 = 22rrΓ(r)Γ(r + 12) πΓ(r + 1)Γ(r + 12) = 22rrΓ(r) πrΓ(r) = 22r π.

And so,

r 12 = 2Γ(2r + 1)πΓ(r + 12)Γ(r + 1)2r r = Γ(2r + 1) Γ(r + 1)Γ(r + 12)2π2r r = 22r π2π2r r = 22r2ππ2r r = 22r+12r r π

as we needed to show. □

45. [HM21] Using the generalized binomial coefficient suggested in exercise 42, find lim rr krk.

From exercise 42 and Stirling’s approximation,

lim rr krk = lim r 1 rk(r + 1)B(k + 1,r k + 1) = lim r Γ(k + 1 + r k + 1) rk(r + 1)Γ(k + 1)Γ(r k + 1) = lim r Γ(r + 2) rk(r + 1)Γ(k + 1)Γ(r k + 1) = 1 Γ(k + 1)lim r (r + 1)Γ(r + 1) rk(r + 1)Γ(r k + 1) = 1 Γ(k + 1)lim r Γ(r + 1) rkΓ(r k + 1) = 1 Γ(k + 1)lim r r! rk(r k)! = 1 Γ(k + 1)lim r 2πr(re)r rk2π(r k)((r k)e)rk = 1 Γ(k + 1)lim r r r k 1 er er ek (r k)krr rk(r k)r = 1 Γ(k + 1)lim r r r k 1 ek ((r k)r)k ((r k)r)r = 1 Γ(k + 1)lim r r r k 1 ek (1 kr)k (1 kr)r = 1 Γ(k + 1) 1 ek lim r 1 (1 kr)r = 1 Γ(k + 1) 1 ek 1 ek = 1 Γ(k + 1).

46. [M21] Using Stirling’s approximation, Eq. 1.2.5-(7), find an approximate value of x+y y , assuming that both x and y are large. In particular, find the approximate size of 2n n when n is large.

Assuming that both x and y are large, using Stirling’s approximation, we find that

x + y y = 1 (x + y + 1)B(x + 1,y + 1) = 1 (x + y + 1)B(y + 1,x + y y + 1) = 1 (x + y + 1)B(y + 1,x + 1) = Γ(x + y + 2) (x + y + 1)Γ(y + 1)Γ(x + 1) = (x + y + 1)Γ(x + y + 1) (x + y + 1)Γ(x + 1)Γ(y + 1) = Γ(x + y + 1) Γ(x + 1)Γ(y + 1) = Γ(x + y + 1) Γ(x + 1)Γ(y + 1) = (x + y)! x!y! 2π(x + y)((x + y)e)x+y 2πx(xe)x2πy(ye)y = x + y 2πxy (x + y)x(x + y)yexey xxyyex+y = 1 2π 1 x + 1 y 1 + y xx 1 + x yy.

In particular, when n is large,

2n n = n + n n 1 2π 1 n + 1 n 1 + n nn 1 + n nn = 1 2π 2 n 2n 2n = 22n πn = 4n πn.

47. [M21] Given that k is an integer, show that

r k r 12 k = 2r k 2r k k 4k = 2r 2k 2k k 4k.

Give a simpler formula for the special case r = 12.

We may prove the equalities.

Proposition. r k r12 k = 2r k 2rk k 4k = 2r 2k 2k k 4k for integer k.

Proof. Let k be an arbitrary integer. We must show that

r k r 12 k = 2r k 2r k k 4k = 2r 2k 2k k 4k.

In the case that k < 0, we have

r k r 12 k = 0 = 2r k 2r k k 4k;

and in the case that k = 0, we have

r k r 12 k = 1 = 2r k 2r k k 4k.

That is, in the case that k 0, we have

r k r 12 k = δk0 = 2r k 2r k k 4k.

In the case that k = r, we have

r k r 12 k = k 12 k = 1 (k 12 + 1)B(k + 1,k 12 k + 1) = 1 (k + 12)B(k + 1,12) = Γ(k + 1 + 12) (k + 12)Γ(k + 1)Γ(12) = Γ(k + 12) Γ(k + 1)Γ(12) = Γ(12)Γ(k + 12) Γ(12)2Γ(k + 1) = Γ(12)Γ(k + 12) πΓ(k + 1) = 2(k + 1)Γ(32)Γ(k + 12) πΓ(32 + k + 12) = 2(k + 1)B(32,k + 12) π = 2 1 (k + 1)B(12 + 1,k 12 + 1)π = 2 k 12π = 22k+1 k 12π4k = 2k k 4k.

It remains to consider the case when 0 < kr. Assuming

r k r 12 k = 2r k 2r k k 4k

we must show that

r k + 1 r 12 k + 1 = 2r k + 1 2r (k + 1) k + 1 4k+1.

As a corollary, note that from Eqs. (7) and (8) with 0kr we have

r k = r k r 1 k 1 = r k r k + 1 r r k 1 = r k + 1 k r k 1.

Then

r k + 1 r 12 k + 1 = r k + 1 r 12 k + 1 = r (k + 1) + 1 k + 1 r (k + 1) 1 r 12 (k + 1) + 1 k + 1 r 12 (k + 1) 1 = (r k)(r k 12) (k + 1)2 r k r 12 k = (r k)(r k 12) (k + 1)2 2r k 2r k k 4k = 4(r k)(r k 12) 4(k + 1)2 2r k 2r k k 4k = 2(2r k)(r k 12) 4(k + 1)2 2r k 2(r k) 2r k 2r k k 4k = 2(2r k)(r k 12) 4(k + 1)2 2r k 2r k 1 k 4k = 1 4 2r (k + 1) + 1 k + 1 2r (k + 1) 1 (2r k 1) (k + 1) + 1 k + 1 2r k 1 (k + 1) 14k = 1 4 2r k + 1 2r k 1 k + 1 4k = 2r k + 1 2r k 1 k + 1 4k+1 = 2r k + 1 2r (k + 1) k + 1 4k+1.

That is, for k an arbitrary integer

r k r 12 k = 2r k 2r k k 4k.

And finally, from Eq. (20)

2r k 2r k k 4k = 2r k 2r k 2k k4k = 2r 2k 2k k 4k

as we needed to show. □

For the special case r = 12, we have the simpler equalities

12 k 12 12 k = 12 k 1 k = 22 k 22 k k 4k = 1 k 1 k k 4k = 22 2k 2k k 4k = 1 2k 2k k 4k

if and only if, from Eq. (17)

12 k = 1 2k 2k k 4k1 k = (1)2k2k(1)1 2k 2k k 4k1 k = 2k k 4k1 k = 2k k 4k(1)kk(1)1 k = 2k k 4k(1)k = 1 4 k2k k .

That is, we have the simpler formula

12 k = 1 4 k2k k .

48. [M25] Show that

k0n k (1)k k + x = n! x(x + 1)(x + n) = 1 xn+x n ,

if the denominators are not zero. [Note that this formula gives us the reciprocal of a binomial coefficient, as well as the partial fraction expansion of 1x(x + 1)(x + n).]

Proposition. k0n k (1)k k+x = n! 0jnx+j = 1 xn+x n .

Proof. Let n and k be arbitrary, nonnegative integers. We must show that

k0n k (1)k k + x = n! 0jnx + j = 1 xn+x n .

First, note that

n! 0jnx + j = n! xn + 1¯ = n! (x + n + 1 1)n+1̲ = n! (x + n)n+1̲ = n!(x + n (n + 1))! (x + n)! = n!(x 1)! (x + n)! = n!x! x(n + x)! = n!(n + x n)! x(n + x)! = 1 xn+x n .

Then, if n = 0,

k0n k (1)k k + x = 0 0 (1)0 0 + x = 1 x = 1 x0+x 0 .

Assuming

k0n k (1)k k + x = n! 0jnx + j = 1 xn+x n

we must show that

k0n + 1 k (1)k k + x = (n + 1)! 0jn+1x + j = 1 xn+1+x n+1 .

But

k0n + 1 k (1)k x + k = 0kn+1n + 1 k (1)k x + k = n + 1 n + 1 (1)n+1 x + n + 1 + 0knn + 1 k (1)k x + k = (1)n+1 x + n + 1 + 0knn + 1 k (1)k x + k = (1)n+1 x + n + 1 + 0kn n k + n k 1 (1)k x + k = (1)n+1 x + n + 1 + 0knn k (1)k x + k + 0kn n k 1 (1)k x + k = (1)n+1 x + n + 1 + 0knn k (1)k x + k + 1kn1n k (1)k+1 x + k + 1 = (1)n+1 x + n + 1 + 0knn k (1)k x + k 1kn1n k (1)k (x + 1) + k = (1)n+1 x + n + 1 n 1 1 x + n n (1)n x + n + 1 + 0knn k (1)k x + k 0knn k (1)k (x + 1) + k = (1)n+1 + (1)n x + n + 1 n 1 1 x + 0knn k (1)k x + k 0knn k (1)k (x + 1) + k = 0knn k (1)k x + k 0knn k (1)k (x + 1) + k = 1 xn+x n 1 (x + 1)n+(x+1) n = n!x! x(n + x)! n!(x + 1)! (x + 1)(n + x + 1)! = n!x!(x + 1)(n + x + 1) x(x + 1)(n + x)!(n + x + 1) n!x(x + 1)! x(x + 1)(n + x + 1)! = n!(x 1)!(n + x + 1) (n + x + 1)! n!x! (n + x + 1)! = n!(x 1)!(n + x + 1) n!x! (n + x + 1)! = n!(x 1)!(n + x + 1) n!(x 1)!x (n + x + 1)! = n!(x 1)!(n + 1) (n + x + 1)! = (n + 1)!(x 1)! (n + x + 1)! = (n + 1)!((n + 1 + x) (n + 1))! x(n + 1 + x)! = 1 xn+1+x n+1

as we needed to show. □

49. [M20] Show that the identity (1 + x)r = (1 x2)r(1 x)r implies a relation on binomial coefficients.

Given

(1 + x)r = (1 x2)r(1 x)r

and the binomial theorem, we have that

0m r mxm = (1 + x)r = (1 x2)r(1 x)r = 0krr k(1)kx2k 0lr l (1)lxl = 0kr 0lr k r l (1)k+lx2k+l = 0kr 0m2kr k r m 2k(1)k+m2kxm = 0kr 2kmr k r m 2k(1)mkxm = 0kr 2kmr k r m 2k(1)m+kxm = 0kr 2kmr k r m 2k(1)m+kxm + 0 = 0kr 2kmr k r m 2k(1)m+kxm + 0m<2kr k r m 2k(1)m+kxm = 0kr 0mr k r m 2k(1)m+kxm = 0m 0krr k r m 2k(1)m+kxm

which implies the relation

r m = 0krr k r m 2k(1)m+k

for integer m.

50. [M20] Prove Abel’s formula, Eq. (16), in the special case x + y = 0.

Proposition. (x + y)n = 0knn k x(x kz)k1(y + kz)nk for integer n 0, x0, x + y = 0.

Proof. Let n be an arbitrary nonnegative integer and x, y, z arbitrary reals such that x0, x + y = 0. We must show that

(x + y)n = 0knn kx(x kz)k1(y + kz)nk;

or equivalently, since x + y = 0, that

δn,0 = 0knn kx(x kz)k1(x + kz)nk.

But by the binomial theorem and Eq. (34)

0knn kx(x kz)k1(x + kz)nk = 0knn kx(x kz)k1(1)nk(x kz)nk = 0knn k (1)nk(x kz)k1+nkx = 0knn k (1)nk(x kz)n1x = 0knn k (1)nkx(x zk)n1 = 0knn k (1)nkx 0mn1n 1 m xn1m(zk)m = 0knn k (1)nk 0mn1n 1 m xnm(1)mzmkm = n!n 1 n xnn(1)nzn = δn,0

as we needed to show. □

51. [M21] Prove Abel’s formula, Eq. (16), by writing y = (x + y) x, expanding the right-hand side in powers of (x + y), and applying the result of the previous exercise.

Proposition. (x + y)n = 0kn k x(x kz)k1(y + kz)nk for integer n 0, x0, x + y = 0.

Proof. Let n be an arbitrary nonnegative integer and x, y, z arbitrary reals such that x0, x + y = 0. We must show that

0kn kx(x kz)k1(y + kz)nk = (x + y)n;

or equivalently, since x + y = x + yy = (x + y) x, that

0kn kx(x kz)k1((x + y) x + kz)nk = (x + y)n.

But from Eq. (6), the binomial theorem, Eq. (20), and exercise 50

0kn kx(x kz)k1((x + y) x + kz)nk = 0k n n kx(x kz)k1((x + y) x + kz)nk = 0k n n kx(x kz)k1((x + y) + (x + kz))nk = 0k n n kx(x kz)k1 0mn k m (x + y)m(x + kz)nkm = 0k 0m n n k n k m (x + y)mx(x kz)k1(x + kz)nkm = 0k 0m n m n m n m k(x + y)mx(x kz)k1(x + kz)nkm = 0m n m(x + y)m 0k n m n m kx(x kz)k1(x + kz)nkm = 0m n m(x + y)mδ nm,0 = n n(x + y)n = (x + y)n

as we needed to show. □

______________________________________________________________________________________________________________________________

A. Hurwitz, Acta Mathematica 26 (1902), 199–203.

52. [HM11] Prove that Abel’s binomial formula (16) is not always valid when n is not a nonnegative integer, by evaluating the right-hand side when n = x = 1, y = z = 1.

We may prove that Abel’s binomial formula

(x + y)n = 0kn kx(x kz)k1(y + kz)nk

is not always valid when n < 0 by evaluating the particular case when n = x = 1, y = z = 1; and

0kn kx(x kz)k1(y + kz)nk = 0k1 k (1)((1) k)k1(1 + k)1k = 0k1 k (1)k(k + 1)k1(k + 1)k1 = 0k1 k (1)k(k + 1)2 = 0k(k + 1)2 from Eq. (17) = 1kk2

where 1kk2 is the Riemann zeta function ζ(2) = π260 = (1 + 1)1 = (x + y)n.

53. [M25] (a) Prove the following identity by induction on m, where m and n are integers:

k=0mr k s n k(nr (r + s)k) = (m + 1)(n m) r m + 1 s n m.

(b) Making use of important relations from exercise 47,

12 n = (1)n 22n 2n n ,12 n = (1)n1 22n(2n 1) 2n n = (1)n1 22n1(2n 1) 2n 1 n δn0,

show that the following formula can be obtained as a special case of the identity in part (a):

k=0m2k 1 k 2n 2k n k 1 2k 1 = n m 2n 2m m 2n 2m n m + 1 2 2n n .

(This result is considerably more general than Eq. (26) in the case r = 1, s = 0, t = 2.)

a)
We may prove the identity by induction.

Proposition. k=0mr k s nk(nr (r + s)k) = (m + 1)(n m) r m+1 s nm for integers m, n.

Proof. Let m and n be arbitrary integers such that m is nonnegative. We must show that

k=0mr k s n k(nr (r + s)k) = (m + 1)(n m) r m + 1 s n m.

If m = 0

k=0mr k s n k(nr (r + s)k) = k=00 r k s n k(nr (r + s)k) = r 0 s n 0(nr (r + s)(0)) = r 0 s n(nr) = s n(nr) = nr s n = nr1!(r 1)! 1!(r 1)! s n = nr (r 1)! 1!(r 1)! s n = n r! 1!(r 1)! s n = nr 1 s n = (1)(n)r 1 s n = (0 + 1)(n 0) r 0 + 1 s n 0 = (m + 1)(n m) r m + 1 s n m.

Then, assuming

k=0mr k s n k(nr (r + s)k) = (m + 1)(n m) r m + 1 s n m

we must show that

k=0m+1 r k s n k(nr (r + s)k) = ((m + 1) + 1)(n (m + 1)) r (m + 1) + 1 s n (m + 1).

But from the inductive hypothesis as well as Eqs. (7) and (8)

k=0m+1 r k s n k(nr (r + s)k) = k=0mr k s n k(nr (r + s)k) + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)(n m) r m + 1 s n m + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)(n m) r m + 1 s n m s 1 n m 1 + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)s r m + 1 s 1 n m 1 + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)s r m + 1 s (n m 1) s s n m 1 + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)(s n + m + 1) r m + 1 s n (m + 1) + r m + 1 s n (m + 1)(nr (r + s)(m + 1)) = (m + 1)(s n + m + 1) + (nr (r + s)(m + 1)) r m + 1 s n (m + 1) = (m + 1)((s n + m + 1) (r + s)) + nr r m + 1 s n (m + 1) = (m + 1)(r n + m + 1) + nr r m + 1 s n (m + 1) = (nr + (r n + m + 1)(m + 1)) r m + 1 s n (m + 1) = (nr r(m + 1) n(m + 1) + (m + 1)2) r m + 1 s n (m + 1) = (n (m + 1))(r (m + 1)) r m + 1 s n (m + 1) = r(n (m + 1))r (m + 1) r r m + 1 s n (m + 1) = r(n (m + 1)) r 1 m + 1 s n (m + 1) = ((m + 1) + 1)(n (m + 1)) r (m + 1) + 1 r 1 m + 1 s n (m + 1) = ((m + 1) + 1)(n (m + 1)) r (m + 1) + 1 s n (m + 1)

as we needed to show. □

b)
We may derive the formula as a special case of the identity in part (a).

Given the relations from exercise 47, since

12 n = (1)n1 22n1(2n 1) 2n 1 n δn0 2n 1 n = 12 n + δn0 22n1(2n 1) (1)n1

and

12 n = (1)n 22n 2n n 2n n = 12 n 22n (1)n

we have that

k=0m2k 1 k 2n 2k n k 1 2k 1 = k=0m 12 k + δk0 22k1(2k 1) (1)k1 2n 2k n k 1 2k 1 = k=0m 12 k + δk0 22k1(1)k2n 2k n k = k=0m 12 k + δk0 22k1(1)k2(n k) n k = k=0m 12 k + δk0 22k1(1)k 12 n k 22(nk) (1)nk = k=0m 12 k + δk0 22n1(1)n 12 n k = (1)n22n1 k=0m 12 k 12 n k + δk0 12 n k = (1)n22n1 k=0m12 k 12 n k + 12 n .

Then, setting r = 1 2, s = 1 2 in the result of (a) yields

k=0m12 k 12 n k(n2 (12 12)k) = k=0m12 k 12 n k(n2) = (m + 1)(n m) 12 m + 1 12 n m

so that, again with the relations from exercise 47, as well as Eqs. (7) and (8),

(1)n22n1 k=0m12 k 12 n k + 12 n = (1)n22n1 2(m + 1)(n m) n 12 m + 1 12 n m + 12 n = (1)n22n12(m + 1)(n m) n (1)m+11 22(m+1)(2(m + 1) 1) 2(m + 1) m + 1 (1)nm 22(nm) 2(n m) n m + (1)n22n1(1)n 22n 2n n = (m + 1)(n m) 22n(2m + 1) 2m + 2 m + 1 2n 2m n m + 1 2 2n n = (m + 1)(n m) 22n(2m + 1) 2m + 2 m + 1 2m + 1 m 2n 2m n m + 1 2 2n n = (m + 1)(n m) 2n(2m + 1) 2m + 1 m 2n 2m n m + 1 2 2n n = (m + 1)(n m) 2n(2m + 1) 2m + 1 2m + 1 m 2m + 1 1 m 2n 2m n m + 1 2 2n n = n m 2n 2m m 2n 2m n m + 1 2 2n n .

Hence

k=0m2k 1 k 2n 2k n k 1 2k 1 = n m 2n 2m m 2n 2m n m + 1 2 2n n .

54. [M21] Consider Pascal’s triangle (as shown in Table 1) as a matrix. What is the inverse of that matrix?

Let

An+1 = [aij]n+1 = i jn+1 = 0 0 0 1 0 n 1 0 1 1 1 n n 0 n 1 n n n+1

represent Pascal’s triangle as a matrix. We want to find another matrix Bn+1 = [bij]n+1 such that

An+1Bn+1 = Bn+1An+1 = In+1 = δij n+1.

But by the definition of matrix multiplication

Bn+1An+1 = 0knbikakj = 0knbikk j = δij = 0ki i k k j (1)ik from Eq. (33) = 0kn i k k j (1)i+k = 0kn(1)i+k i k k j .

Hence, for arbitrary k, 0 k n

bikk j = (1)i+k i k k j bik = (1)i+k i k

and in particular for k = j

bij = (1)i+j i j

as we wanted to find, so that the inverse matrix is given by

Bn+1 = [bij]n+1 = (1)i+j i jn+1 = 0 0 0 1 (1)n 0 n 1 0 1 1 (1)1+n 1 n (1)nn 0 (1)n+1n 1 n n n+1.

55. [M21] Considering each of Stirling’s triangles (Table 2) as matrices, determine their inverses.

Let

An+1 = [aij]n+1 = i jn+1 = 0 0 0 1 0 n 1 0 1 1 1 n n 0 n 1 n n n+1

represent Stirling’s triangle of the first kind as a matrix. We want to find another matrix Bn+1 = [bij]n+1 such that

An+1Bn+1 = Bn+1An+1 = In+1 = δij n+1.

But by the definition of matrix multiplication

Bn+1An+1 = 0knbikakj = 0knbikk j = δij = δji = 0ki i k k j (1)ik from Eq. (47) = 0kn(1)i+k i k k j .

Hence, for arbitrary k, 0 k n

bikk j = (1)i+k i k k j bik = (1)i+k i k

and in particular for k = j

bij = (1)i+j i j

as we wanted to find, so that the inverse matrix is given by

Bn+1 = [bij]n+1 = (1)i+j i jn+1 = 0 0 0 1 (1)n 0 n 1 0 1 1 (1)1+n 1 n (1)nn 0 (1)n+1n 1 n n n+1.

Similarly, let

An+1 = [a ij] n+1 = i jn+1 = 0 0 0 1 0 n 1 0 1 1 1 n n 0 n 1 n n n+1

represent Stirling’s triangle of the second kind as a matrix. We want to find another matrix Bn+1 = [bij]n+1 such that

An+1B n+1 = B n+1A n+1 = I n+1 = δij n+1.

But by the definition of matrix multiplication

Bn+1A n+1 = 0knbika kj = 0knbikk j = δij = δji = 0ki i k k j (1)ik from Eq. (47) = 0kn(1)i+k i k k j .

Hence, for arbitrary k, 0 k n

bikk j = (1)i+k i k k j bik = (1)i+k i k

and in particular for k = j

bij = (1)i+j i j

as we wanted to find, so that the inverse matrix is given by

Bn+1 = [b ij] n+1 = (1)i+j i jn+1 = 0 0 0 1 (1)n 0 n 1 0 1 1 (1)1+n 1 n (1)nn 0 (1)n+1n 1 n n n+1.

56. [20] (The combinatorial number system.) For each integer n = 0,1,2,,20, find three integers a,b,c for which n = a 3 + b 2 + c 1 and a > b > c 0. Can you see how this pattern can be continued for higher values of n?

We may evaluate the largest values for a, b, and c that satisfy the constraint such that a > b > c 0.

abcn




2 1 0 0
3 1 0 1
3 2 0 2
3 2 1 3
4 1 0 4
4 2 0 5
4 2 1 6
4 3 0 7
4 3 1 8
4 3 2 9
5 1 0 10
5 2 0 11
5 2 1 12
5 3 0 13
5 3 1 14
5 3 2 15
5 4 0 16
5 4 1 17
5 4 2 18
5 4 3 19
6 1 0 20

This pattern can be continued for higher values of n by the following method: let a be the largest integer that satisfies a 3 n; b the largest that satisfies b 2 n a 3 ; and c that satisfies c 1 n a 3 b 2.

57. [M22] Show that the coefficient am in Stirling’s attempt at generalizing the factorial function, Eq. 1.2.5-(12), is

(1)m m! k1(1)km 1 k 1 ln k.

Proposition. am = (1)m m! 1k(1)km1 k1 ln k in Stirling’s generalization of the factorial function.

Proof. Stirling’s generalization of the factorial function is

ln n! = 0mam+1 0jm(n j).

We must show that

am = (1)m m! 1k(1)km 1 k 1 ln k.

But given

0jm j (1)mj = 0jm j (1)mj

we have

0jm j (1)mj ln n! = 0jm j (1)mj 0kak+1 0jk(n j) = 0jm j (1)mj 0kak+1jk+1̲ from Eq. 1.2.5-18 = 0jm j (1)mj 0kak+1 j! (j (k + 1))! from Eq. 1.2.5-21 = 0jm j (1)mj 0kak+1(k + 1)! j! (k + 1)!(j (k + 1))! = 0jm j (1)mj 0kak+1(k + 1)! j k + 1 = 0jm j (1)mj 0kakk!j k a00!j 0 = 0jm j (1)mj 0kakk!j k a0 = 0jm j (1)mj 0kakk!j k (1)0 0! 1k(1)k 1 k 1ln k = 0jm j (1)mj 0kakk!j k 0 = 0jm j (1)mj 0kakk!j k = 0jm j (1)mj kk!akj k = kk!ak j j k m j (1)mj = m!am from Eq. (33)

And so

am = 1 m! 0jm j (1)mj ln n! = 1 m! 0jm j (1)m+j ln n! = (1)m m! 0jm j (1)j ln n! = (1)m m! 0jm j (1)j 1kn ln k = (1)m m! 0j 1knm j (1)j ln k = (1)m m! 1k kjm j (1)j ln k = (1)m m! 1k ln k kjm j (1)j = (1)m m! 1k ln k jmm j (1)j jk1m j (1)j = (1)m m! 1k ln k (1 + 1)m jk1m j (1)j from Eq. (13) = (1)m m! 1k ln k 0 jk1m j (1)j = (1)m m! 1k ln k(1) jk1m j (1)j = (1)m m! 1k ln k(1)(1)k1m 1 k 1 from Eq. (18) = (1)m m! 1k(1)km 1 k 1 ln k.

Therefore

am = (1)m m! 1k(1)km 1 k 1 ln k

as we needed to show. □

58. [M23] (H. A. Rothe, 1811.) In the notation of Eq. (40), prove the “q-nomial theorem”:

(1 + x)(1 + qx)(1 + qn1x) = kn kqqk(k1)2xk.

Also find q-nomial generalizations of the fundamental identities (17) and (21).

In order to prove the “q-nomial theorem”, we define

r kq = 1jk(1 qrj+1) 1jk(1 qj) = 1jk1 qrj+1 1 qj

and assume q-nomial symmetry

n kq = n n kq

as well as the two q-Pascal identities

n + 1 k q = n kq + n k 1qqn+1k

and

n + 1 k q = n kqqk + n k 1q.

Proposition. 0kn1(1 + qkx) = 0knn k qqk(k1)2xk.

Proof. Let n and q be an arbitrary nonnegative integer and real number, respectively. We must show that

0kn1(1 + qkx) = 0knn kqqk(k1)2xk

If n = 0

0kn1(1 + qkx) = 0k1(1 + qkx) = 1 = 1 1 = 1j0(1 q0j+1) 1j0(1 qj) = 0 0q = 0 0qq(0)(1)2x0 = 0k0 0 kqqk(k1)2xk = 0knn kqqk(k1)2xk.

Then, assuming

0kn1(1 + qkx) = 0knn kqqk(k1)2xk

we must show that

0kn(1 + qkx) = 0kn+1n + 1 k qqk(k1)2xk.

But

0kn(1 + qkx) = (1 + qnx) 0kn1(1 + qkx) = (1 + qnx) 0knn kqqk(k1)2xk = 0knn kqqk(k1)2xk + qnx 0knn kqqk(k1)2xk = 0knn kqqk(k1)2xk + 0knn kqqn+k(k1)2xk+1 = 0knn kqqk(k1)2xk + 1kn+1 n k 1qqn+(k1)(k2)2xk = 0kn+1n kqqk(k1)2xk + 0kn+1 n k 1qqn+(k1)(k2)2xk = 0kn+1 n kq + n k 1qqn+(k1)(k2)2k(k1)2 qk(k1)2xk = 0kn+1 n kq + n k 1qqn+1k qk(k1)2xk = 0kn+1n + 1 k qqk(k1)2xk.

Hence

0kn1(1 + qkx) = 0knn kqqk(k1)2xk

as we needed to show. □

We may also find q-nomial generalizations of the fundamental identities (17) and (21).

For (17), we have

r kq = 1jk1 qrj+1 1 qj = 1jk 1 1 1 qrj+1 1 qj = (1)k 1jk 1 qrj+1 1 qj = (1)k 1jkqrj+11 qr+j1 1 qj = (1)k 1jkqrj+1 1 qj 1jk1 qr+j1 = (1)k 1jkqrj+1 1 qj 1j+k+1k1 qr+j1 = (1)k 1jkqrj+1 1 qj 1j+k+1k1 qkr(j+k+1) = (1)k 1jkqrj+1 1 qj 1jk1 qkrj = (1)k 1jkqrj+11 qkrj 1 qj = (1)k 1jkqr 1jkqj1 1jk1 qkrj 1 qj = (1)k qkr (q11 qk1 )k 1jk1 qkrj 1 qj = (1)k qkr qk(k1)2 1jk1 qkrj 1 qj = (1)kqkrk(k1)2 1jk1 qkrj 1 qj = (1)kqkrk(k1)2 1jk1 qkr1j+1 1 qj = (1)kqkrk(k1)2k r 1 k q = (1)kk r 1 k qqkrk(k1)2

so that the q-nomial generalizations of the fundamental identity (17) is

r kq = (1)kk r 1 k qqkrk(k1)2.

For (21), the q-nomial theorem

0kn1(1 + qkx) = 0knn kqqk(k1)2xk

gives us

0nr+sr + s n qqn(n1)2xn = 0nr+s1(1 + qnx) = 0kr1(1 + qkx) rkr+s1(1 + qkx) = 0kr1(1 + qkx) 0krs1(1 + qkx) = 0kr1(1 + qkx) 0ks1(1 + qk+rx) = 0kr1(1 + qkx) 0ks1(1 + qkqrx) = 0krr kqqk(k1)2xk 0kss kqqk(k1)2(qrx)k = 0krr kqqk(k1)2xk 0kss kqqk(k1)2qrkxk = 0krr kqqk(k1)2xk 0nks s n kqq(nk)(nk1)2qr(nk)xnk = 0nr+s 0krr kq s n kqqk(k1)2q(nk)(nk1)2qr(nk) xn = 0nr+s 0krr kq s n kqqk22k2+n22nk2kn2+k22n2+k2+rnrk xn = 0nr+s 0krr kq s n kqqk2+n22nkn2+rnrk xn.

Equating coefficients yields

r + s n qqn(n1)2 = 0krr kq s n kqqk2+n22nkn2+rnrk
if and only if r + s n q = 0krr kq s n kqqk2+n22nkn2+rnrk qn(n1)2 = 0krr kq s n kqqk2+n22nkn2+rnrkn22+n2 = 0krr kq s n kqqk2nk+rnrk = 0krr kq s n kqq(rk)(nk) = 0kss kq r n kqq(sk)(nk) = 0krr kq s n kqq(sn+k)k

so that the q-nomial generalizations of the fundamental identity (21) is

r + s n q = 0krr kq s n kqq(rk)(nk) = 0krr kq s n kqq(sn+k)k.

______________________________________________________________________________________________________________________________

H. A. Rothe, Systematisches Lehrbuch der Arithmetik (Leipzig: 1811), xxix; F. Schweins, Analysis (Heidelberg: 1820), §151; D. E. Knuth, J. Combinatorial Theory A10 (1971), 178–180; G. Gasper and M. Rahman, Basic Hypergeometric Series (Cambridge Univ. Press, 1990); C. F. Gauss, Commentationes societatis regiæ scientiarum Gottingensis recentiores 1 (1808), 147–186; Cauchy, Comptes Rendus Acad. Sci. 17 (Paris, 1843), 523–531; C. G. J. Jacobi, Crelle 32 (1846), 197–204; E. Heine, Crelle 34 (1847), 285–328.

59. [M25] A sequence of numbers Ank, n 0, k 0, satisfies the relations An0 = 1, A0k = δ0k, Ank = A(n1)k + A(n1)(k1) + n k for nk > 0. Find Ank.

We have that

Ank = (n + 1)n k n k + 1

and may prove this by induction.

Proposition. Ank = (n + 1)n k n k+1.

Proof. Let n and k be arbitrary integers such that n 0, k 0, and nk > 0. We must show that

Ank = (n + 1)n k n k + 1.

First note that

An0 = (n + 1)n 0 n 0 + 1 = n + 1 n = 1

and

A0k = (0 + 1)0 k 0 k + 1 = δ0k

as required. If n = 1, we have

A1k = A0k + A0(k1) + 1 k = δ0k + δ0(k1) + 1 k = 0 k 0 k + 1 + 0 k 1 0 k + 1 k = 0 k + 0 k 1 + 1 k 0 k + 1 + 0 k = 1 k + 1 k 1 k + 1 = 21 k 1 k + 1 = (1 + 1)1 k 1 k + 1.

Then, assuming

Ank = (n + 1)n k n k + 1

we must show that

A(n+1)k = ((n + 1) + 1)n + 1 k n + 1 k + 1.

But

A(n+1)k = Ank + An(k1) + n + 1 k = (n + 1)n k n k + 1 + (n + 1) n k 1 n k + n + 1 k = (n + 1) n k + n k 1 + n + 1 k n k + 1 + n k = (n + 1)n + 1 k + n + 1 k n + 1 k + 1 = (n + 2)n + 1 k n + 1 k + 1 = ((n + 1) + 1)n + 1 k n + 1 k + 1

as we needed to show. □

60. [M23] We have seen that n k is the number of combinations of n things, k at a time, namely the number of ways to choose k different things out of a set of n. The combinations with repetitions are similar to ordinary combinations, except that we may choose each object any number of times. Thus, the list (1) would be extended to include also aaa, aab, aac, aad, aae, abb, etc., if we were considering combinations with repetition. How many k-combinations of n objects are there, if repetition is allowed?

The number of k-combinations of n objects, if repetition is allowed, is given by

n + k 1 k .

The number of k-combinations of n objects, if repetition is not allowed is simply the number of integer solutions (o1,o2,,ok) such that 0 < o1 < o2 < < ok < n + 1, known to be

|{oi : 0 < o1 < o2 < < ok < n + 1}| = n k.

If repetitions are allowed, we want to determine

|{oi : 0 < o1 o2 ok < n + 1}| = |{oi : 0 < o1 < o2 + 1 < < ok + k 1 < n + k 1 + 1}| = |{oi : 0 < o 1 < o 2 < < o k < n + k}| = n + k 1 k

and hence the result.

________________________________________________________________________________

H. F. Sherk, Crelle 3 (1828), 97; W. A. Förstemann, Crelle 13 (1835), 237.

61. [M25] Evaluate the sum

kn + 1 k + 1 k m(1)km,

thereby obtaining a companion formula for Eq. (55).

We have

kn + 1 k + 1 k m(1)km = k n n k + 1 + n k k m(1)km from Eq. (46) = n k n k + 1 k m(1)km + kn k k m(1)km = n k n k + 1 k m(1)km + (1)nm kn k k m(1)nk = n k n k + 1 k m(1)km + (1)nmδ mn from Eq. (47) = n k n k + 1 k m(1)km + δ mn.

If n < m then k < m and

n k n k + 1 k m(1)km + δ mn = 0 + 0 = 0.

If n = m then k < m and

n k n k + 1 k m(1)km + δ mn = 0 + 1 = 1.

Otherwise, if n > m

n k n k + 1 k m(1)km + δ mn = n k n k + 1 k m(1)km = n!m!

which we may prove by induction.

Proposition. n k n k+1 k m(1)km = n!m! for 0 m < n.

Proof. Let m and n be arbitrary nonnegative integers such that m < n. We must show that

n k n k + 1 k m(1)km = n!m!

If n = 1, 0 m < n = 1m = 0 and

n k n k + 1 k m(1)km = k 1 k + 1 k 0(1)k = k 1 k + 1 k 0(1)k = 1 1 0 0(1)0 = 1 = 1!0! = n!m!

Then, assuming

n k n k + 1 k m(1)km = n!m!

we must show that

(n + 1) kn + 1 k + 1 k m(1)km = (n + 1)!m!

But

(n + 1) kn + 1 k + 1 k m(1)km = (n + 1) k n n k + 1 + n k k m(1)km = (n + 1) kn n k + 1 k m(1)km + (n + 1) kn k k m(1)km = (n + 1)n k n k + 1 k m(1)km + (n + 1) kn k k m(1)km = (n + 1)n!m! + (n + 1) kn k k m(1)km = (n + 1)n!m! + (n + 1) kn k k m(1)nk(1)kmn+k = (n + 1)n!m! + (n + 1)(1)m+n kn k k m(1)nk = (n + 1)n!m! + (n + 1)(1)m+nδ mn from Eq. (47) = (n + 1)n!m! + 0 = (n + 1)n!m! = (n + 1)!m!

as we needed to show. □

And so, since

kn + 1 k + 1 k m(1)km = 0 if n < m 1 if n = m n!m!otherwise

we have that

kn + 1 k + 1 k m(1)km = [n m]n!m!

62. [M23] The text gives formulas for sums involving a product of two binomial coefficients. Of the sums involving a product of three binomial coefficients, the following one and the identity of exercise 31 seem to be most useful:

k(1)kl + m l + k m + n m + k n + l n + k = (l + m + n)! l!m!n! ,integer l,m,n 0.

(The sum includes both positive and negative values of k.) Prove this identity. [Hint: There is a very short proof, which begins by applying the result of exercise 31.]

Proposition. k(1)kl+m l+k m+n m+k n+l n+k = (l+m+n)! l!m!n! , integer l,m,n 0.

Proof. Let l,m,n be arbitrary nonnegative integers. We must show that

k(1)kl + m l + k m + n m + k n + l n + k = (l + m + n)! l!m!n! .

But from exercise 31

km r + s k n + r s n k r + k m + n = r m s n

we have for m = m + k,n = l k,r = m + n,s = n + l,k = j that

k(1)kl + m l + k m + n m + k n + l n + k = k(1)kl + m l + k r m s s n = k(1)kl + m l + k r m s n = k(1)kl + m l + k km r + s k n + r s n k r + k m + n = k(1)kl + m l + k jm + k m n + n + l j l k + m + n n l l k j m + n + j m + k + l k = k,j(1)kl + m l + k l + k j m k l k j m + n + j m + l = k,j(1)k (l + m)! (m k)!(l + k)! (l + k)! (l + k j)!j! (m k)! (m l + j)!(l k j)! (m + n + j)! (n + j l)!(m + l)! = k,j(1)k 1 (l + k j)!j! 1 (m l + j)!(l k j)! (m + n + j)! (n + j l)! = k,j(1)k 1 (l j k)!(l j + k)! (m + n + j)! j!(m l + j)!(n + j l)! = k,j(1)k (2l 2j)! (2l 2j (l j + k))!(l j + k)!(2l 2j)! (m + n + j)! j!(m l + j)!(n + j l)! = k,j(1)k 2l 2j l j + k (m + n + j)! (2l 2j)!j!(m l + j)!(n + j l)! = k,j(1)k 2l 2j l j + k 1 (2(l j))! (m + n + j)! j!(m l + j)!(n + j l)! = k,j(1)k 2l 2j l j + k(0 2(l j))! 0! (2(l j))!(0 2(l j))! (m + n + j)! j!(m l + j)!(n + j l)! = k,j(1)k 2l 2j l j + k(2(j l))! 0 2(l j) (m + n + j)! j!(m l + j)!(n + j l)! = k,j(1)k 2l 2j l j + k(2(j l))!δlj (m + n + j)! j!(m l + j)!(n + j l)! = k(1)k 2l 2l l l + k(2(l l))! (m + n + l)! l!(m l + l)!(n + l l)! = k(1)k0 k0!(m + n + l)! l!m!n! = (1)0(l + m + n)! l!m!n! = (l + m + n)! l!m!n!

as we needed to show. □

______________________________________________________________________________________________________________________________

A. C. Dixon, Messenger of Math. 20 (1891), 79–80; A. C. Dixon, Proc. London Math. Soc. 35 (1903), 285–289; L. J. Rogers, Proc. London Math. Soc. 26 (1895), 15–32, §8; P. A. MacMahon, Quarterly Journal of Pure and Applied Math. 33 (1902), 274–288; John Dougall, Proc. Edinburgh Math. Society 25 (1907), 114–132.

63. [M30] If l, m, and n are integers and n 0, prove that

j,k(1)j+kj + k k + l r j n k s + n j k m j = (1)ln + r n + l s r m n l.

Proposition. j,k(1)j+kj+k k+l r j n k s+njk mj = (1)ln+r n+l sr mnl, integers l, m, and n 0.

Proof. Let l, m, and n be arbitrary integers such that n 0. We must show that

j,k(1)j+kj + k k + l r j n k s + n j k m j = (1)ln + r n + l s r m n l.

But as a polynomial in arbitary reals x and y, we have

l,m j,k(1)j+kj + k l + k r j n k s + n j k m j xlym = m j,k(1)j+k lj + k l + k xlr j n k s + n j k m j ym = m j,k(1)j+k l+kj + k l + k xlr j n k s + n j k m j ym = m j,k(1)j+k l+kj + k l + k xl+k xk r j n k s + n j k m j ym = m j,k(1)j+k(1 + x)j+k xk r j n k s + n j k m j ym = j,k(1)j+k(1 + x)j+k xk r j n k ms + n j k m j ym = j,k(1)j+k(1 + x)j+k xk r j n k mjs + n j k m j ym = j,k(1)j+k(1 + x)j+k xk r j n k mjs + n j k m j ymjyj = j,k(1)j+k(1 + x)j+k xk r j n k (1 + y)s+njkyj = jr j (1)j(1 + x)jyj (1 + y)j kn k (1)k (1 + x)k (1 + y)kxk(1 + y)s+n = jr j (1 + x)y 1 + y j kn k 1 + x (1 + y)xk(1 + y)s+n = 1 (1 + x)y 1 + y r 1 1 + x (1 + y)xn(1 + y)s+n = 1 + y (1 + x)y 1 + y r (1 + y)x (1 + x) (1 + y)x n(1 + y)s+n = 1 xy 1 + y r (1)(1 xy) (1 + y)x n(1 + y)s+n = (1 xy)r (1 + y)r (1)n(1 xy)n (1 + y)nxn (1 + y)s+n = (1 xy)r (1 + y)r (1)n(1 xy)n xn (1 + y)s = (1)n(1 xy)n+r(1 + y)sr xn .

Continuing,

(1)n(1 xy)n+r(1 + y)sr xn = (1)n n+ln+r n+l (xy)n+l(1 + y)sr xn = (1)n ln+r n+l (xy)n+l(1 + y)sr xn = l(1)2n+ln + r n + l (1 + y)srxlyn+l = l(1)ln + r n + l (1 + y)srxlyn+l = l(1)ln + r n + l mnl s r m n lymnlxlyn+l = l(1)ln + r n + l m s r m n lymnlxlyn+l = l,m(1)ln + r n + l s r m n lxlym.

Equating coefficients yields the result

j,k(1)j+kj + k k + l r j n k s + n j k m j = (1)ln + r n + l s r m n l

as we needed to show. □

______________________________________________________________________________________________________________________________

CMath, exercises 5.83 and 5.106.

64. [M20] Show that n m is the number of ways to partition a set of n elements into m nonempty disjoint subsets. For example, the set {1,2,3,4} can be partitioned into two subsets in 4 2 = 7 ways: {1,2,3}{4}; {1,2,4}{3}; {1,3,4}{2}; {2,3,4}{1}; {1,2}{3,4}; {1,3}{2,4}; {1,4}{2,3}. Hint: Use Eq. (46).

Let p(n,m) denote the number of ways to partition a set of n elements into m nonempty disjoint subsets for nonnegative integers m, n. If n = 0, then clearly

p(0,m) = δ0m = 0 m.

Otherwise, if n > 0, we seek the number of partitions which contain the set n, given by p(n 1,m 1) and the number of partitions in which n has been inserted into sets with other elements, given by mp(n 1,m). That is, from Eq. (46) and induction,

p(n,m) = p(n 1,m 1) + mp(n 1,m) = n m,

and hence the claim.

65. [HM35] (B. F. Logan.) Prove Eqs. (59) and (60).

We may prove Eq. (59).

Proposition. zr = k r rkzrk̲ for Re (z) > 0.

Proof. Let r,z be arbitrary complex numbers such that Re (z) > 0. We must show that

zr = k r r kzrk̲.

In the case that Re (r) < 1, by definition and since Re (z) > 0,

Γ(1 r) =0ett1r1dt =0ettrdt = zr1 zr10ettrdt = 1 zr10zr1ettrdt = 1 zr10zr1ezt(zt)rdzt = 1 zr10zr1r+1ezttrdt = 1 zr10ezttrdt

if and only if

zr = z Γ(1 r)0ezttrdt = z Γ(1 r)01(1 u)z(ln (1 u))rd(ln (1 u)) for et = 1 u = z Γ(1 r)01(1 u)z1 ln 1 1 urdu = z Γ(1 r)01(1 u)z1ur ur ln 1 1 urdu = z Γ(1 r)01(1 u)z1ur 1 uln 1 1 urdu.

From Eq. (6.51)1

1 uln 1 1 ur = r kr + k r uk (r + k)k+1̲ = r k r r k uk (r + k)k+1̲ = r k r r k Γ(r)uk Γ(r + k + 1) = k r r k Γ(1 r)uk Γ(r + k + 1)

and given the definition of the β function as

0(1 u)z1ukrdu = β(k r + 1,z) = Γ(1 r + k)Γ(z) Γ(1 r + k + z)

we have that

zr = z Γ(1 r)01(1 u)z1ur 1 uln 1 1 urdu = z Γ(1 r)01(1 u)z1ur k r r k Γ(1 r)uk Γ(r + k + 1)du = k r r k z Γ(r + k + 1)01(1 u)z1ukrdu = k r r k z Γ(r + k + 1) Γ(1 r + k)Γ(z) Γ(1 r + k + z) = k r r k zΓ(z) Γ(1 r + k + z) = k r r k Γ(z + 1) Γ(z r + k + 1) = k r r k z! (z r + k)! = k r r kzrk̲

which establishes the case Re (r) < 1. Then, assuming

zr = k r r kzrk̲

we must show that

zr+1 = k r + 1 r + 1 kzr+1k̲.

But from the recurrence relations for falling factorial powers

zzrk̲ = zrk+1̲ + (r k)zrk̲

and Eq. (46) we have that

zr+1 = zzr = z k r r kzrk̲ = k r r kzzrk̲ = k r r k(zrk+1̲ + (r k)zrk̲) = k r r kzrk+1̲ + k1 r r (k 1)(r (k 1))zr(k1)̲ = k r r kzrk+1̲ + k r r k + 1(r k + 1)zrk+1̲ = k r r k + (r k + 1) r r k + 1zrk+1̲ = k r + 1 r + 1 kzr+1k̲

as we needed to show. □

We may also prove Eq. (60).

Proposition. zr̲ = 0km r rk(1)kzrk + O(zrm1).

Proof. Let r,z be arbitrary complex numbers. We must show that

zr̲ = 0km r r k(1)kzrk + O(zrm1).

By Euler-Maclaurin summation for Stirling’s approximation2 we have that

1k<z ln (k) = zln (z) z + σ ln (z) 2 + 1km B2k 2k(2k 1)z2k1 + φm,z B2m+2 (2m + 2)(2m + 1)z2m+1, 1k<zr ln (k) = (z r)ln (z r) (z r) + σ ln (z r) 2 + 1km B2k 2k(2k 1)(z r)2k1 + φm,zr B2m+2 (2m + 2)(2m + 1)(z r)2m+1

for an arbitrary positive integer m, constant σ, “Stirling’s constant,” Bernoulli numbers Bk, and 0 < φm,x < 1, so that

ln zr̲ zr = ln z! zr(z r)! = ln (z!) ln ((z r)!) rln (z) = rln (z) + 1kz ln (k) 1kzr ln (k) = rln (z) + ln (z) ln (z r) + 1k<z ln (k) 1k<zr ln (k) = (1 r)ln (z) ln (z r) + 1k<z ln (k) 1k<zr ln (k) = (1 r)ln (z) ln (z r) + zln (z) z + σ ln (z) 2 + 1km B2k 2k(2k 1)z2k1 + φm,z B2m+2 (2m + 2)(2m + 1)z2m+1 (z r)ln (z r) + (z r) σ + ln (z r) 2 1km B2k 2k(2k 1)(z r)2k1 φm,zr B2m+2 (2m + 2)(2m + 1)(z r)2m+1 = r + (z r + 12)ln (z) (z r + 12)ln (z r) + 1km B2k 2k(2k 1) z(2k1) (z r)(2k1) + B2m+2 (2m + 2)(2m + 1) φm,zz(2m+1) φ m,zr(z r)(2m+1) = r (z r + 12)ln (1 rz) + 1km B2k 2k(2k 1) z(2k1) (z r)(2k1) + B2m+2 (2m + 2)(2m + 1) φm,zz(2m+1) φ m,zr(z r)(2m+1) .

That is, so that ln zr̲ zr is a series in which each coefficient of zk is a polynomial in r; and so similarly for the exponential

zr̲ zr = 0kmck(r)zk + O(zm1)

with coefficients ck(r), polynomials in r, and with asymptotic bounds O(zm1), if and only if

zr̲ = 0kmck(r)zrk + O(zrm1).

From Eq. (44) for r restricted to the integers

zr̲ = 0krr k(1)rkzk = 0kr r r k(1)kzrk,

and since r rk is a polynomial in r of degree 2k whenever k is a nonnegative integer, the coefficients of zrk hold for arbitrary complex r such that

ck(r) = r r k(1)k.

Therefore

0kmck(r)zrk + O(zrm1) = 0km r r k(1)kzrk + O(zrm1).

and hence the result

zr̲ = 0km r r k(1)kzrk + O(zrm1).

______________________________________________________________________________________________________________________________

AMM 99 (1992), 410–422.

66. [HM30] Suppose x, y, and z are real numbers satisfying

x n = y n + z n 1,

where x n 1, y n 1, z > n 2, and n is an integer 2. Prove that

x n 1 y n 1 + z n 2 if and only if y z; x n + 1 y n + 1 + z n if and only if y z.

Proposition. x n1 y n1 + z n2 iff y z, x n+1 y n+1 + z n iff y z.

Proof. Let x, y, and z be arbitrary real numbers and n an arbitrary integer 2 such that

x n = y n + z n 1,

x n 1, y n 1, and z > n 2. We must show that both

x n 1 y n 1 + z n 2y z

and

x n + 1 y n + 1 + z ny z.

We will first show the former. Since y z,

x n = y n + z n 1 z n + z n 1 z + 1 n ,

and so x z + 1. Given the identities

a + n 1 n 1 = a + 0 (1)(n 1) n 1 = 0jn1a (1)j j 0 (1)((n 1) j) (n 1) j a a (1)jfrom Eq. (26) = 0jn1a + j j n 1 j n 1 j a a + j = 0jn1a + j j a a + j = 0jn1 (a + j)! j!(a + j j)! a a + j = 0jn1 a(a + j)! (a + j)j!a! = 0jn1 (a + j 1)! j!(a + j 1 j)! = 0jn1a + j 1 j

and

a + b n = a + (b n) (1)n n = 0jna (1)j j (b n) (1)(n j) n j a a (1)j from Eq. (26) = 0jna + j j b j n j a a + j = 0jna + j j a + j a + j j b j n j = 0jna + j 1 j b j n j from Eq. (8)

for arbitrary integers a,b; and letting x = t + x, y = t + y, z = t + n 1,

x n = t + x n = 0jnt + j 1 j x j n j , y n = t + y n = 0jnt + j 1 j y j n j , z n 1 = t + n 1 n 1 = 0jn1t + j 1 j ;

we have that

0 = y n + z n 1 x n = 0jnt + j 1 j y j n j + 0jn1t + j 1 j 0jnt + j 1 j x j n j = t + n 1 n y n n n t + n 1 n x n n n + 0jn1t + j 1 j y j n j + 1 x j n j = t + n 1 n t + n 1 n + 0jn1t + j 1 j y j n j + 1 x j n j = 0jn1t + j 1 j φnj

where

φi = y n + i i + 1 x n + i i .

Similarly, since t increases by one as n decreases by one,

y n 1 + z n 2 x n 1 = 0jn2t + 1 + j 1 j φn1j = 1jn1t + j 1 j 1 φnj = 1jn1t + j 1 j 1 φnj = 1jn1 j t + j 1 j + 1 t + j 1 j φnj from Eqs. (7), (8) = 1jn1j t t + j 1 j φnj = 0jn1j t t + j 1 j φnj

with the understanding that in the case t = 0, we define 0 t = 0. Then, for all i, 1 i n 1, since x yx y by hypothesis and x = x t y t z + 1 t = n,

φi1 = y n + i 1 i 1 + 1 x n + i 1 i 1 = i y n + i y n + i i + 1 i x n + i x n + i i i x n + i y n + i i + i x n + i i x n + i x n + i i = i x n + i y n + i i + 1 x n + i i = i x n + iφi 0.

but

φn = y n + n n + 1 x n + n n = y n + 1 x n = y n + n 1 n 1 x n = y t n + z t n 1 x t n 0.

And so finally,

y n 1 + z n 2 x n 1 = 0jn1j t t + j 1 j φnj 0jn11 t t + j 1 j φnj = 1 t 0jn1t + j 1 j φnj = 0

and hence the former result.

We will then show the latter, and it is sufficient to show that if

x n + 1 y n + 1 z n = 0

implies

d dz x n + 1 y n + 1 z n 0,

then

x n + 1 y n + 1 + z ny z.

But assuming

x n + 1 y n + 1 z n = x n n + 1 x n y n n + 1 y n z (n 1) n z n 1 = x n n + 1 y n + z n 1 y n n + 1 y n z n + 1 n z n 1 = x n n + 1 y n + x n n + 1 z n 1 y n n + 1 y n z n + 1 n z n 1 = x n n + 1 z n 1 + x y n + 1 y n z n + 1 n z n 1 = 0

and since x yx y 0 by hypothesis, we have that

x n n + 1 z n 1 + x y n + 1 y n z n + 1 n z n 1 = 0 x n n + 1 z n 1 z n + 1 n z n 1 0 x n n + 1 z n 1 z n + 1 n z n 1 x n n + 1 z n + 1 n .

Also, with d dz z n1 = d dz x n, and given that d dnn! = d dnΓ(n + 1) = n! γ + 1kn1 k for the Euler-Mascheroni constant γ,

d dx x nx n = 1 n! d dx x! (x n)! x! n!(x n)! = 1 n! (x n)! d dxx! x! d dx(x n)! ((x n)!)2 x! n!(x n)! = (x n)! d dxx! x! d dx(x n)! x!(x n)! = (x n)!x! γ + 1kx1 k x!(x n)! γ + 1kxn1 k x!(x n)! = γ + 1kx1 k + γ 1kxn1 k = xn+1kx1 k = 0kn1 1 x k

and

n n + 1 d dz z n 1 z n 1 = n (n + 1)(n 1)! d dz z! (z (n 1))! z! (n 1)!(z (n 1))! = n (n + 1)(n 1)! (z (n 1))! d dzz! z! d dz(z (n 1))! ((z (n 1))!)2 z! (n 1)!(z (n 1))! = n n + 1 (z (n 1))! d dzz! z! d dz(z (n 1))! z!(z (n 1))! = n n + 1 (z (n 1))!z! γ + 1kz1 k z!(z (n 1))! γ + 1kz(n1) 1 k z!(z (n 1))! = n n + 1 γ + 1kz1 k + γ 1kz(n1) 1 k = n n + 1 z(n1)+1kz1 k = n n + 1 0kn2 1 z k.

Also, since

1 = 1 d dx x n d dx x n = d dz z n 1 d dz z n 1 d dx x n d dz z n 1 d dx x n = d dz z n 1 d dx x n dx dz = d dz z n 1

and since for arbitrary integers k 0, n n + 1 k n+1 k n, we have that

x n n + 1 z n + 1 n k n + 1 k n x n + k n + 1 + k n + 1 z n + 1 n + k n. x n + k n + 1 z n + 1 + k n 1 x n + k n n + 1 1 z n + 1 + k 0kn1 1 x k n n + 1 0kn1 1 z k 0kn1 1 x k n n + 1 0kn2 1 z k d dx x nx n n n + 1 d dz z n 1 z n 1 z n 1 n n + 1 x n d dz z n 1 d dx x n z n 1 n n + 1 x n dx dz 1 n z n 1 1 n + 1 x n dx dz 1 n + 1 x n dx dz 1 n z n 1 1 n + 1 x n dx dz 1 n z n 1 0.

Then

d dz x n + 1 y n + 1 z n = d dz x n n + 1 x n y n n + 1 y n z (n 1) n z n 1 = d dz x n n + 1 x n d dz y n n + 1 y n d dz z (n 1) n z n 1 = d dx dx dz x n n + 1 x n d dz z (n 1) n z n 1 = x n n + 1 d dx x n dx dz + 1 n + 1 x n dx dz z (n 1) n d dz z n 1 1 n z n 1 = x n n + 1 d dz z n 1 + 1 n + 1 x n dx dz z (n 1) n d dz z n 1 1 n z n 1 = 1 n + 1 x n dx dz 1 n z n 1 + x n n + 1 z n + 1 n d dz z n 1 x n n + 1 z n + 1 n d dz z n 1 0

and hence the latter result. □

______________________________________________________________________________________________________________________________

L. Lovász, Combinatorial Problems and Exercises (1993), Problem 13.31(a); R. M. Redheffer, AMM 103 (1996), 62–64.

67. [M20] We often need to know that binomial coefficients aren’t too large. Prove the easy-to-remember upper bound

n k ne k k,when n k 0.

Proposition. n k ne k k.

Proof. Let n and k be arbitrary integers such that n k 0. We must show that

n k ne k k.

In the case that k = 0, if we adopt the convention that ne k 0 = 1, then

n 0 = 1 ne k 0.

Otherwise, since clearly

nk̲ nk

and from exercise 1.2.5-24

kk ek1 k!iff 1 k! ek1 kk ,

we have that

n k = nk̲ k! nk k! ek1 kk nk = 1 e nkek kk = 1 e ne k k ne k k.

Hence

n k ne k k

for all integers n k 0 as we needed to show. □

68. [M25] (A. de Moivre.) Prove that, if n is a nonnegative integer,

kn kpk(1 p)nk|k np| = 2np n nppnp(1 p)n+1np.

Proposition. kn k pk(1 p)nk|k np| = 2np n nppnp(1 p)n+1np.

Proof. Let n be a nonnegative integer. We must show that

kn kpk(1 p)nk|k np| = 2np n nppnp(1 p)n+1np.

But

kn kpk(1 p)nk|k np| = k<npn kpk(1 p)nk|k np| + npkn kpk(1 p)nk|k np| = k<npn kpk(1 p)nk(np k) + npkn kpk(1 p)nk(k np) = k<npn kpk(1 p)nk (k + 1)n k k + 1 p k(1 p) + npkn kpk(1 p)nk k(1 p) (k + 1)n k k + 1 p = k<np(k + 1) n k + 1pk+1(1 p)n+1(k+1) kn kpk(1 p)n+1k + npk kn kpk(1 p)n+1k (k + 1) n k + 1pk+1(1 p)n+1(k+1) = np n nppnp(1 p)n+1np + np n nppnp(1 p)n+1np = 2np n nppnp(1 p)n+1np

as we needed to show. □

______________________________________________________________________________________________________________________________

De Moivre, Miscellanea Analytica (1730), 101; H. Poincaré, Calcul des Probabilités (1896), 56–60; P. Diaconis and S. Zabell, Statistical Science 6 (1991), 284–302.