Exercises from Section 1.2.5

Tord M. Johnson

March 27, 2014

1. [00] How many ways are there to shuffle a 52-card deck?

As we have 52 choices for the first card, 51 for the second, and so on, we simply have 52! ways to shuffle a 52-card deck. 52! is the 68 decimal digit number

80658175170943878571660636856403766975289505440883277824000000000000.

2. [10] In the notation of Eq. (2), show that pn(n1) = pnn, and explain why this happens.

In the notation of Eq. (2), since

pnk = nk+1jnj

we have that

pnn = 1jnj = 2jnj = n(n1)+1jnj = pn(n1).

That is, after choosing the (n 1)th element, we have no choice left for the last element.

3. [10] What permutations of {1,2,3,4,5} would be constructed from the permutation 3 1 2 4 using Methods 1 and 2, respectively?

We can construct permutations of the set {1,2,3,4,5} from the permutation 3 1 2 4 using either method.

In Method 1, we insert 5 in all possible positions to obtain

5 3 1 2 4, 3 5 1 2 4, 3 1 5 2 4, 3 1 2 5 4, and 3 1 2 4 5.

In Method 2, we start with an intermediary set of permutations

3 1 2 4 1 2, 3 1 2 4 3 2, 3 1 2 4 5 2, 3 1 2 4 7 2, and 3 1 2 4 9 2,

which are finally renamed as

4 2 3 5 1, 4 1 3 5 2, 4 1 2 5 3, 3 1 2 5 4, and 3 1 2 4 5.

4. [13] Given the fact that log 101000! = 2567.60464 , determine exactly how many decimal digits are present in the number 1000!. What is the most significant digit? What is the least significant digit?

Since the number of decimal digits in a number n is given by log 10n + 1, log 101000! = 2567.60464 implies that 1000! has 2568 decimal digits.

The most significant digit is given by 1000! 1025681 , but since log 104 = 0.60206 and log 105 = 0.69897 ,

log 101000! = 2567.60464 2567 + log 104 log 101000! < 2567 + log 105 log 10102567 + log 104 log 101000! < log 10102567 + log 105 log 10 4 102567 log 101000! < log 10 5 102567 log 104 log 10 1000! 102567 < log 105 4 1000! 1025681 < 5,

and so, the most significant digit is 1000! 1025681 = 4.

The least significant digit is intuitively 0, since the factorial is some number multiplied by a factor of 1000. We can determine precisely how many zeros using Eq. (8), since

μ2 = k>0 1000 2k = 1k9 1000 2k = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994

and

μ5 = k>0 1000 5k = 1k4 1000 5k = 200 + 40 + 8 + 1 = 249

giving us that for some arbitrary integer z not divisible by 10, 1000! = 2994 5249z = 2745z 10249; that is, 1000! is a number that ends with 249 zeros.

________________________________________________________________________________

[Scripta Mathematica 21 (1955), 266–267]

5. [15] Estimate 8! using the more exact version of Stirling’s approximation:

n! 2πn n en 1 + 1 12n.

We may estimate 8! as

8! 2π8 8 e8 1 + 1 12(8) = 4π16777216 e8 97 96 = 203423744π 3e8 40318.

6. [17] Using Eq. (8), write 20! as a product of prime factors.

Since the primes that divide 20 are 2, 3, 5, 7, 11, 13, 17, and 19, we may determine the multiplicity of the prime factors of 20! as

μ2 = k>0 20 2k = 1k4 20 2k = 10 + 5 + 2 + 1 = 18,
μ3 = k>0 20 2k = 1k2 20 2k = 6 + 2 = 8,
μ5 = k>0 20 5k = 1k1 20 5k = 4,
μ7 = k>0 20 7k = 1k1 20 7k = 2,
μ11 = k>0 20 11k = 1k1 20 11k = 1,
μ13 = k>0 20 13k = 1k1 20 13k = 1,
μ17 = k>0 20 17k = 1k1 20 17k = 1,

and

μ19 = k>0 20 19k = 1k1 20 19k = 1,

so that 20! = 218 38 54 72 11 13 17 19.

7. [M10] Show that the “generalized terminal” function in Eq. (10) satisfies the identity x? = x + (x 1)? for all real numbers x.

Proposition. x? = x + (x 1)? for all real numbers x.

Proof. Let x be an arbitrary real number. We must show that

x? = x + (x 1)?.

But by Eq. (10)

x? = 1 2x(x + 1) = x x + 1 2x(x + 1) = x + 2x 2 + 1 2x(x + 1) = x + 1 2(x2 + x 2x) = x + 1 2(x2 x) = x + 1 2(x 1)x = x + 1 2(x 1)((x 1) + 1) = x + (x 1)?

as we needed to show. □

8. [HM15] Show that the limit in Eq. (13) does equal n! when n is a nonnegative integer.

When n is a nonnegative integer, we have

lim m mnm! 1km(n + k) = lim m mnm! (n + m)!n! = lim mn!mnm! (m + n)! = lim m n!mn (m + n)!m! = lim m n!mn 1kn(m + k) = lim mn! 1kn m m + k = n!lim m 1kn m m + k = n!.

9. [M10] Determine the values of Γ(1 2) and Γ(1 2), given that 1 2! = π2.

Given that 1 2! = π2, we have that

Γ 1 2 = 1 2! 1 2 = π 2 2 1 = π

and that

Γ 1 2 = 2 1Γ 1 2 = 2π

since Γ(n + 1) = nΓ(n).

10. [HM20] Does the identity Γ(x + 1) = xΓ(x) hold for all real numbers x? (See exercise 7.)

The identity Γ(x + 1) = xΓ(x) holds for all real numbers x, except when x is zero or a negative integer, since

Γ(x + 1) = lim m mxm! 1km(x + k) = lim mmx(x + m) x(x + m) mx1m! 2km+1((x 1) + k) = lim m mx x + m mx1m! 1km((x 1) + k) = xlim m m m + x mx1m! 1km((x 1) + k) = xlim m mx1m! 1km((x 1) + k) = xΓ(x).

11. [M15] Let the representation of n in the binary system be n = 2e1 + 2e2 + + 2er, where e1 > e2 > > er 0. Show that n! is divisible by 2nr but not by 2nr+1.

Given n = 1jr2ej, we may find the exact multiplicity of the prime factor 2 from Eq. (8) as:

μ = i>0 n 2i = 1ir 1jr2ej 2ei = 1ir 0jr2ej 2ei = 1jr 1ij2ej 2ei = 1jr2ej 1ij 1 2ei = 1jr2ej 2ej(2ej 1) 2 1 = 1jr2ej 2ej(2ej 1) = 1jr(2ej 1) = 1jr2ej 0jr1 = n 1jr1 = n r.

That is, n! is divisible by 2n1, but not by 2nr+1.

12. [M22] (A. Legendre, 1808.) Generalizing the result of the previous exercise, let p be a prime number, and let the representation of n in the p-ary number system be n = akpk + ak1pk1 + + a1p + a0. Express the number μ of Eq. (8) in a simple formula involving n, p, and a’s.

Given n = 0jkajpj, we may express the number μ from Eq. (8) as:

μ = i>0 n pi = 1ik 0jkajpj pi = 1ik 0jkajpj pi = 0jk 1ijajpj pi = 0jkajpj 1ij 1 pi = 0jkajpjpj(pj 1) p 1 = 0jkajpj pj pj 1 p 1 = 0jkajpj 1 p 1 = 0jkaj(pj 1) p 1 = 0jkajpj 0jkaj p 1 = n 0jkaj p 1 .

13. [M23] (Wilson’s theorem, actually due to Leibniz, 1682.) If p is prime, then (p 1)! mod p = p 1. Prove this, by pairing off numbers among {1,2,,p 1} whose product modulo p is 1.

Proposition. If p is prime, (p 1)! mod p = p 1.

Proof. Let p be an arbitrary prime. We must show that

(p 1)! mod p = p 1.

By exercise 1.2.4-19, for each integer k, 1 < k < p 1, there is another integer k such that

kk 1(modp)

allowing us to ’pair off numbers’ as

(p 2)!1! 1(modp).

Also, clearly,

1 1(modp)

and

(p 1) p 1(modp).

And so,

(p 1)! p 1(modp)

or equivalently

(p 1)! mod p = p 1

as we needed to show. □

14. [M28] (L. Stickelberger, 1890.) In the notation of exercise 12, we can determine n! mod p in terms of the p-ary representation, for any positive integer n, thus generalizing Wilson’s theorem. In fact, prove that n!pμ (1)μa0!a1!ak!(modulo p).

Proposition. n!pμ (1)μ 0ikai!(modp).

Proof. Let n and p be arbitrary positive integers such that p is prime, n = 0ikaipi, and μ = 1jk n pj. We must show that

n!pμ (1)μ 0ikai!(modp).

First consider the trivial case k = 0, so that n = a0 and μ = 0. Then clearly

a0! a0!(modp) a0!p0 (1)0 0i0ai!(modp) n!pμ (1)μ 0ikai!(modp).

Then, assuming as an inductive hypothesis for nk = 0ikaipi and μk = 1ik nk pi that

nk!pμk (1)μk 0ikai!(modp),

we must show for nk+1 = ak+1pk+1 + nk and μk+1 = nk+1 pk+1 + μk that

nk+1!pμk+1 (1)μk+1 0ik+1ai!(modp).

(Note that the equality for μk+1 holds since nk+1 has grown by a multiple of p; namely, ak+1pk.)

But by Wilson’s theorem, all the terms between nk + 1 and nk+1 that are not multiples of p may be collected into sets of size p 1 whose product is congruent to 1 modulo p, and there are precisely nk+1 pk+1 of these products, with ak+1 left over, congruent to ak+1! modulo p. That is

nk+1ink+1ipnk+1 pk+1 (1)nk+1 pk+1 ak+1!(modp).

Multiplying this by the inductive hypothesis yields

nk+1ink+1ipnk+1 pk+1 nk!pμk (1)nk+1 pk+1 ak+1!(1)μk 0ikai!(modp) nk! nk+1ink+1ipnk+1 pk+1 +μk (1)nk+1 pk+1 +μk ak+1! 0ikai!(modp) nk+1!pμk+1 (1)μk+1 0ik+1ai!(modp).

Therefore

n!pμ (1)μ 0ikai!(modp)

as we needed to show. □

15. [HM15] The permanent of a square matrix is defined by the same expansion as the determinant except that each term of the permanent is given a plus sign while the determinant alternates between plus and minus. Thus the permanent of

abc d e f ghi

is aei + bfg + cdh + gec + hfa + idb. What is the permanent of

1 × 11 × 21 × n 2 × 1 2 × 2 2 × n n × 1 n × 2 n × n ?

The permanent of a square matrix may be defined recursively as

perm ([aij]n) = a11 if n = 1 1jnaij + perm (submatrix (aij))otherwise.

In the case that aij = i × j, we may simply add

(1 × 1) + (2 × 2) + + (n × n) = (n!)2,

and we do this for n! terms, yielding a total sum of

n!(n!)2 = (n!)3.

16. [HM15] Show that the infinite sum in Eq. (11) does not converge unless n is a nonnegative integer.

The infinite sum in Eq. (11),

k0 0jk(1)j j! 0j<k(n j),

does not converge unless n is a nonnegative integer, since if n < 0, the product 0j<k(n j) never vanishes as the coefficients

lim k 0jk(1)j j! = 1 e.

(In the case that n 0, the product eventually vanishes with a factor of zero.)

17. [HM20] Prove that the infinite product

n1(n + α1)(n + αk) (n + β1)(n + βk)

equals Γ(1 + β1)Γ(1 + βk)Γ(1 + α1)Γ(1 + αk), if α1 + + αk = β1 + + βk and if none of the β’s is a negative integer.

Proposition. n1 1ikn+αi n+βi = 1ikΓ(1+βi) Γ(1+αi) if 1ikαi = 1ikβi and βi 0 for 1 i k.

Proof. Let αi and βi be arbitrary integer sequences such that 1ikαi = 1ikβi and βi 0 for 1 i k. We must show that

n1 1ikn + αi n + βi = 1ikΓ(1 + βi) Γ(1 + αi).

But

1ikΓ(1 + βi) Γ(1 + αi) = lim m 1ikm1+βim!0jm(1 + αi + j) m1+αim!0jm(1 + βi + j) = lim m 1ikmβi0jm(1 + αi + j) mαi0jm(1 + βi + j) = lim mm 1ikβi m 1ikαi 1ik 0jm(1 + αi + j) 0jm(1 + βi + j) = lim m 1ik 0jm1 + αi + j 1 + βi + j = lim m 0jm 1ik1 + αi + j 1 + βi + j = lim m 1nm 1ikn + αi n + βi = n1 1ikn + αi n + βi

as we needed to show. □

18. [M20] Assume that π2 = 2 1 2 3 4 3 4 5 6 5 6 7 . (This is “Wallis’s product,” obtained by J. Wallis in 1655, and we will prove it in exercise 1.2.6-43.) Using the previous exercise, prove that 1 2! = π2.

Proposition. 1 2! = π2.

Proof. We must show that

1 2! = π2.

But according to exercise 17 with α1 = α2 = 0, β1 = 12, and β2 = 12 so that 1i2αi = 1i2βi and βi 0 for 1 i 2,

π 2 = 1 2 π 2 = 1 2 n1 2n 2n 1 2n 2n + 1 = 1 2 n1 n n 1 2 n n + 1 2 = 1 2 n1n + α1 n + β1 n + α2 n + β2 = 1 2 n1 1k2n + αk n + βk = 1 2 1k2Γ(1 + βk) Γ(1 + αk = 1 2 1k2Γ(1 + βk) Γ(1 + αk) = 1 2 Γ 1 + β1 Γ 1 + α1 Γ 1 + β2 Γ 1 + α2 = 1 2 Γ 1 1 2 Γ 1 Γ 1 + 1 2 Γ 1 = 1 2 Γ 1 2 Γ 1 Γ 3 2 Γ 1 = 1 2Γ 1 2Γ 3 2 = 2 2Γ 3 2Γ 3 2 = Γ 3 22 = Γ 3 2 = 1 2!

as we needed to show. □

______________________________________________________________________________________________________________________________

[Wallis’s own heuristic “proof” can be found in D. J. Struik’s Source Book in Mathematics (Harvard University Press, 1969), 244–253.]

19. [HM22] Denote the quantity appearing after “lim m” in Eq. (15) by Γm(x). Show that

Γm(x) =0m 1 t mmtx1dt = mx01(1 t)mtx1dt,if x > 0.

Proposition. Γm(x) =0m 1 t m mtx1dt = mx 01(1 t)mtx1dt if x > 0.

Proof. Let x be an arbitrary positive real number so that x > 0. We must show that

Γm(x) =0m 1 t mmtx1dt = mx01(1 t)mtx1dt.

But by substituting mt for t

0m 1 t mmtx1dt =0tt 1 mt m m(mt)x1dmt =01 1 tmmxtx1dt = mx01 1 tmtx1dt.

Then, let

fm(x) =01 1 tmtx1dt.

We may prove by induction on m that

fm(x) = m! 0km(x + k).

If m = 0, clearly

f0(x) =01 1 t0tx1dt =01tx1dt = tx x 01 = 1x x 0x x = 1 0 x = 1 x = 0! 0k0(x + k).

Then, assuming

fm(x) = m! 0km(x + k),

we must show that

fm+1(x) = (m + 1)! 0km+1(x + k).

But by integration by parts, since d dx tx x = tx1 and d dt(1 t)m+1 = (m + 1)(1 t)m,

fm+1(x) =01(1 t)m+1tx1dt = (1 t)m+1tx x 01 01 (m + 1)(1 t)mtx x dt = (1 1)m+11x x (1 0)m+10x x + m + 1 x 01(1 t)mtxdt = 0 0 + m + 1 x 01(1 t)mtxdt = m + 1 x fm(x + 1).

And so, by the inductive hypothesis,

fm+1(x) = m + 1 x fm(x + 1) = m + 1 x m! 0km(x + 1 + k) = (m + 1)m! x 1km+1(x + k) = (m + 1)! 0km+1(x + k),

so that

fm(x) = m! 0km(x + k).

Finally

0m 1 t mmtx1dt = mx01(1 t)mtx1dt = mxf m(x) = mx m! 0km(x + k) = mxm! 0km(x + k) = Γm(x)

as we needed to show. □

20. [HM21] Using the fact that 0 et (1 tm)m t2etm, if 0 t m, and the previous exercise, show that Γ(x) =0ettx1dt, if x > 0.

Proposition. Γ(x) =0ettx1dt, if x > 0.

Proof. Let x be an arbitrary positive real number such that x > 0. We must show that

Γ(x) =0ettx1dt.

Let

g(x) =0ettx1dt.

It is sufficient to show that g(x) Γ(x) = 0.

Note that if 0 t m,

1 + x ex 1 ± tm e±tm (1 ± tm)m e±t

and from exercise 1.2.1-9,

et (1 tm)m = et(1 tm)met et(1 tm)m(1 + tm)m = et(1 t2m2)m et(1 t2m)

so that

0 et (1 tm)m t2etm.

Then since x + 1 2,

0 et (1 tm)m tx+1etm 0 0met (1 tm)mdt 1 m0mtx+1etdt < 1 m0tx+1etdt 0 0et (1 tm)mdt 1 m0tx+1etdt 0 0et (1 tm)mdt 0 0et (1 tm)mdt = 0 0ettx1dt 0(1 tm)mtx1dt = 0 g(x) Γ(x) = 0

as we needed to show. □

21. [HM25] (L. F. A. Arbogast, 1800.) Let Dxku represent the kth derivative of a function u with respect to x. The chain rule states that Dx1w = Du1wDx1u. If we apply this to second derivatives, we find Dx2w = Du2w(Dx1u)2 + Du1wDx2u. Show that the general formula is

Dxnw = j=0n k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 Dujw n! k1!(1!)k1kn!(n!)kn(Dx1u)k1 (Dxnu)kn .

Proposition. Dxnf = 0jn k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 n!Dgjf 1in(Dxig)ki ki!(i!)ki .

Proof. Let f be an arbitrary function of g, g an arbitarary function of x, and n a positive integer. We must show that that the nth derivative of f with respect to x is

Dxnf = 0jn k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 n!Dgjf 1in(Dxig)ki ki!(i!)ki .

As done by T. A.1 , it suffices to analyze the coefficients for any function f. Let f = epg(x). By Taylor’s theorem for an arbitrary h,

epg(x+h) = n0hn n! Dxnf.

But also, by expanding g(x + h) and developing the product,

epg(x+h) = epg(x) n1epDxnghn n! = n0hn 0jnpjepg(x) k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 1in(Dxig)ki ki!(i!)ki = n0hn 0jnDgjf k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 1in(Dxig)ki ki!(i!)ki .

Equating these two yields

n0hn n! Dxnf = n0hn 0jnDgjf k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 1in(Dxig)ki ki!(i!)ki 1 n!Dxnf = 0jnDgjf k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 1in(Dxig)ki ki!(i!)ki Dxnf = 0jn k1+k2++kn=j k1+2k2++nkn=n k1,k2,,kn0 n!Dgjf 1in(Dxig)ki ki!(i!)ki

and hence the result. □

______________________________________________________________________________________________________________________________

[Bull. Amer. Math. Soc. 44 (1938), 395–398]

[Du Calcul des Dérivations (Strasbourg: 1800), §52]

[Quarterly J. Math. 1 (1857), 359-360]

see the paper by I. J. Good, Annals of Mathematical Statistics 32 (1961), 540–541.

22. [HM20] Try to put yourself in Euler’s place, looking for a way to generalize n! to noninteger values of n. Since (n + 1 2)!n! times ((n + 1 2) + 1 2)!(n + 1 2)! equals (n + 1)!n! = n + 1, it seems natural that (n + 1 2)!n! should be approximately (n). Similarly, (n + 1 3)!n! should be n3. Invent a hypothesis about the ratio (n + x)!n! as n approaches infinity. Is your hypothesis correct when x is an integer? Does it tell anything about the appropriate value of x! when x is not an integer?

Observing that

(n + 1 2)! n! n and (n + 1 3)! n! n3,

we might hypothesize that

lim n(n + x)! n!nx = 1.

When x is an integer, the equality holds, as

lim n(n + x)! n!nx = lim n 1kx(n + k) nx = lim nnx 1kx 1 + k n nx = lim n 1kx 1 + k n = 1.

It tells us something about the appropriate value of x! when x is not an integer as well, since

1 = lim n(n + x)! n!nx = x!lim n 1kn(x + k) n!nx x! = lim n nxn! 1kn(x + k) = Γ(x + 1).

23. [HM20] Prove (16), given that πz n=1(1 z2n2) = sin πz.

Proposition. (z)!Γ(z) = π sin πz for z not an integer.

Proof. Let z be an arbitrary real number, not an integer. We must show that

(z)!Γ(z) = π sin πz.

But given

πz m1 1 z2 m2 = sin πz πz sin πz = 1 m1 1 z2 m2

we have

z(z)!Γ(z) = zlim m mzm! 1km(z + k)lim m mzm! z 1km(z + k) = lim m mzm!mzm! 1km(z + k)(z + k) = lim m (m!)2 1kmk2 1 z k 1 + z k = lim m (m!)2 (m!)2 1km 1 z k 1 + z k = lim m 1 1km 1 z2 k2 = 1 m1 1 z2 k2 = πz sin πz.

Finally, dividing both sides by z yields

(z)!Γ(z) = π sin πz

as we needed to show. □

24. [HM21] Prove the handy inequalities

nn en1 n! nn+1 en1 ,integer n 1.

[Hint: 1 + x ex for all real x; hence (k + 1)k e1k k(k 1).]

Proposition. nn en1 n! nn+1 en1 for integer n 1.

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

nn en1 n! nn+1 en1 .

Note that since 1 + x ex for all real x,

1 + 1 k e1 k k + 1 k e1 k (k + 1)k kk e,

and

1 1 k + 1 e 1 k+1 k k + 1 e 1 k+1 kk+1 (k + 1)k+1 e1 (k + 1)k+1 kk+1 e.

Then

nn n! = 1knn 1knk = 1knnkk1 1knkkk1 = 1knnkk1 1knkk = nn nn 1knkk1 1kn1kk = 2knkk1 1kn1kk = 1kn1(k + 1)k 1kn1kk = 1kn1(k + 1)k kk 1kn1e = en1,

and so

nn en1 n!.

Then also

nn+1 n! = 1kn+1n 1knk = 1kn+1nkk 1knkkk = 1kn+1nkk 1knkk+1 = nn+1 nn+1 1knkk 1kn1kk+1 = 2knkk 1kn1kk+1 = 1kn1(k + 1)k+1 1kn1kk+1 = 1kn1(k + 1)k+1 kk+1 1kn1e = en1,

and so

n! nn+1 en1 .

Therefore,

nn en1 n! nn+1 en1

as we needed to show. □

25. [M20] Do factorial powers satisfy a law analogous to the ordinary law of exponents, xm+n = xmxn?

Factorial powers satisfy laws analogous to the ordinary law of exponents. In particular,

xm+n̲ = xm̲(x m)n̲ xm + n¯ = xm¯(x + m)n¯,

since

xm+n̲ = x! (x (m + n))! = x! (x m n)! = x! (x m n)! (x m)! (x m)! = x! (x m)! (x m)! (x m n)! = xm̲(x m)n̲

and

xm + n¯ = = Γ(x + m + n) Γ(x) = Γ(x + m + n) Γ(x) Γ(x + m) Γ(x + m) = Γ(x + m) Γ(x) Γ(x + m + n) Γ(x + m) = xm¯(x + m)n¯.