4710 Binomial coefficients homework assignment PDF

Preview

Summary

A short introduction to the Binomial coefficients (and bijective counting proofs)
Any student of probability theory should be familiar with the basic properties and interpretations of the binomial coefficients.
Factorial, Stirling formula
Foranintegern,n!=n×(n−1)×(n−2)×···×3×2×1. T...

Description

Math 4710

Binomial coefficients

Spring 2020

A short introduction to the Binomial coefficients (and bijective counting proofs) Any student of probability theory should be familiar with the basic properties and interpretations of the binomial coefficients. Factorial, Stirling formula For an integer n, n! = n × (n − 1) × (n − 2) × · · · × 3 × 2 × 1. This is a large number for even moderately large n (e.g., n = 52). The convention is that 0! = 1. Abraham De Moivre (1667-1754) (author of “The Doctrine of Chance,” 1718) figured out that √ n! ∼ cnn e−n n for some constant c. (This means that the ratio of the two sides, left and right, tends to one). Question 1 What is the approximation of (n − 1)! ? This is your chance to consult one of the greatest book ever written in mathematics, An Introduction to Probability Theory and its Applications, Volume 1, by William Feller, first published in 1950. This great book was written while Feller was Professor of Mathematics at Cornell (1945-1950). At the time, the Department of Mathematics was in White Hall. On pages 52-54 (I am using the third edition), you will find a delightful elementary proof of the statement discovered by De Moivre. Page 54 gives a two sided inequality for n! that is valid for all n and captures how good Stirling approximation is. James Stirling, (1692-1770), figured out what the mysterious constant c is, namely, √ √ n! ∼ 2πnn e−n n.   ? Question 2 How large is 2n n Binomial coefficients Recall that Ckn =

  n n! n × (n − 1) × · · · × (n − k + 2) × (n − k + 1) = = k! k !(n − k )! k

counts the number of different ways to choose k things among n things. Here n, k are integers and   when k > n, Ckn = 0. However, there is another point of view which allows us to define xk for any real x. There is a notation for the numerator of the right-most fraction in the equation displayed above, namely, (n)k = n × (n − 1) × · · · × (n − k + 1).

This quantity makes perfect sense if we replace n by a real x. Indeed, for any non-negative integer  k, (x)k is a polynomial in x of degree k. We can thus define kx for any real x and non-negative 1

Math 4710

Binomial coefficients

Spring 2020

x = (x)k /k!. Verify that this extended definition is compatible with the convention integer nk by k that k = 0 whenever n is an integer greater than k . The binomial theorem says that (a + b)n =

n X

Cinai bn−1 =

i=0

n   X n i n−i ab . i i=1

Can you prove it using the definition of Cin (the number of different ways to choose i things among n things)? You probably have heard about the “Pascal triangle” which is related to the formula       n n+1 n + = . k−1 k k Why is this true? (give two proofs, one using algebra, one using counting). The binomial formula for (1 + t)a , −1 < t < 1, and an arbitrary real a (due to Newton) is (1 + t)a = 1 +

      ∞ X a 2 a 3 (a)k k a t+ t + t + ··· = t . 1 2 3 k! k=0

This formula takes advantage of the notation (a)k explained above (for any real a). The extended    k . This is a description of the Taylor series of binomial coefficients ka are defined by ka = (a) k! (1 + t)a at t = 0. √ Question 3 Write down explicitly what this gives you for 1 + x.  Question 4 What is the largest of the binomial coefficients kn for a given n (there is a small difference between the cases n = 2ℓ is even and n = 2ℓ + 1 is odd). Pn   Pn 2n n−1 ? What is Question 5 Why is it that i=0 (−1)i ni = 0? And why is it that i=0 2i = 2 Pn 2n+1  the value of i=1 2i+1 ? For each of the following identities, give a proof using counting (you can also try a proof using algebra):    n  . • nk = n−k n−1 n • k k = n k−1 .       • k2 kn = n2 n−2 . k−2   • 1 × n + 2 × (n − 1) + · · · + (n − 1) × 2 + n × 1 = n+2 . 3 2

Math 4710

Binomial coefficients

n+m

n

Spring 2020

m 

= nm. 2 2n  • = n . k=0 k Pk n m  n+m  • = . ℓ=0 ℓ k−ℓ k Pn  ℓ   n+1  • ℓ=m m = m+1 . •

2

Pn

−

2

n2

−

The last one of these identities is somewhat more difficult. We end by reaching towards “higher mathematics”: The Γ function is defined for z = x + iy, x > 0 (if you are uncomfortable with complex numbers, you can set y = 0) , by Z ∞ tz−1 e−t dt. Γ(z) = 0

Why does this integral make sense? What is Γ(1). Use integration by parts to show that Γ(x + 1) = xΓ(x). Why is it true that Γ(n) = (n − 1)!?

3...