1. Prove the binomial theorem
Recall that if F(z) = ∑ akzk, then we can extract ak by differentiating F k times, dividing by k!, and setting the result to 0, i.e. ak = (1/k!) dk/dzk F(z) |z=0.
Prove by induction on k that dk/dzk (1+z)n = n(k) (1+z)n-k for all k in ℕ.
Use this fact to show that if (1+z)n = ∑ akzk, then ak = n(k)/k!.
Use the preceding to prove that (x+y)n = ∑ (n(k)/k!) xkyn-k.
1.1. Solution
Base case: k=0, and we have d0/dz0 (1+z)n = (1+z)n = n(0) (1+z)n-0. Induction step: Suppose dk-1/dzk-1 (1+z)n = n(k-1) (1+z)n-k+1. Then dk/dzk (1+z)n = d/dz (dk-1/dzk-1 (1+z)n) = d/dz (n(k-1) (1+z)n-k+1) = n(k-1)(n-k+1) (1+z)n-k = n(k) (1+z)n-k.
Using the coefficient-extraction rule, we have ak = (1/k!) dk/dzk (1+z)n |z=0 = (1/k!) n(k) (1+z)n-k |z=0 = n(k)1n-k/k! = n(k)/k!.
Let z = y/x. Then (1+z)n = (1+y/x)n = ∑ (n(k)/k!) (y/x)k = ∑ (n(k)/k!) x-kyk. Now multiply both sides by xn to get xn(1+y/x)n = (x+y)n = ∑ (n(k)/k!) xn-kyk.
2. A triple identity
Recall Vandermonde's identity (see BinomialCoefficients):
![\[
{n+m \choose k} = \sum_r {n \choose r}{m \choose k-r}.
\]](/pinewiki/CS202/2007/Assignments/HW04/Solutions?action=AttachFile&do=get&target=latex_43f9c4df46051a53d7dbb17fc91875c727f1d212_p1.png "\[
{n+m \choose k} = \sum_r {n \choose r}{m \choose k-r}.
\]")
A combinatorial interpretation of this identity is that if you want to pick k things out of the union of an n-element set and an m-element set, you can do so by first picking a value r, and then choosing r things from the first set and k-r from the second.
Consider the following alleged identity, which we will call the triple Vandermonde identity or TVI for short:
![\[
{n+m+p \choose k} = \sum_{r_1} \sum_{r_2} {n \choose r_1} {m \choose r_2} {p \choose k-r_1-r_2}.
\]](/pinewiki/CS202/2007/Assignments/HW04/Solutions?action=AttachFile&do=get&target=latex_cd9b5f220086cc1235fc0f05c81fc4e1c99cffc2_p1.png "\[
{n+m+p \choose k} = \sum_{r_1} \sum_{r_2} {n \choose r_1} {m \choose r_2} {p \choose k-r_1-r_2}.
\]")
- Give a combinatorial interpretation of TVI.
- Prove TVI is true.
2.1. Solution
- The interpretation is that if we want to pick k things out of three sets, we can choose the number of things r₁ we will take from the first set, the number r₂ we will take from the second set, and then for each such choice we can pick out a particular set of things by taking r₁ from the first, r₂ from the second, and k-r₁-r₂ from the third.
- The easiest proof is probably just to use Vandermonde's identity twice:
In the first step we can move (n choose r₁) out of the r₂ summation because (n choose r₁) doesn't depend on r₂.
An alternative proof might involve waving our magic generating function stick over the equation (1+z)n+m+p = (1+z)n(1+z)m(1+z)p, but it's not clear that the result would be more intelligible than the approach above.
3. Sequence differences
Suppose you have a generating function F(z) = ∑ anzn. Write an expression in terms of F for the generating function G of the sequence given by the rule bn = an-an-1.
- Prove the identity
![\[
{n \choose k} - {n \choose k-1}
= {n-1 \choose k} - {n-1 \choose k-2}.
\]](/pinewiki/CS202/2007/Assignments/HW04/Solutions?action=AttachFile&do=get&target=latex_c73ba0b5317bf2dae0f17458d284f915715dee7d_p1.png "\[
{n \choose k} - {n \choose k-1}
= {n-1 \choose k} - {n-1 \choose k-2}.
\]")
3.1. Solution
- From the shift and sum rules for generating functions we get G = (1-z)F.
Recall that the generating function for (n choose k) is (1+z)n. Applying the previous result, we get a generating function for (n choose k) - (n choose k-1) of (1-z)(1+z)n. Now use (1-z)(1+z) = 1-z² to rewrite this as (1-z)²(1-z)n-1, which splits into (1+z)n-1, the generating function for (n-1 choose k), and -z²(1+z)n-1, the generating function for -(n-1 choose k-2). (You can also do this using Pascal's identity and a bit of algebra.)
4. Rabbits
Let's imagine that Fibonacci's famous rabbits are so fecund that they produce two daughters in their second year instead of just one.
Specifically, let T(n) satisfy the recurrence T(n) = T(n-1) + 2T(n-2), with T(1) = T(0) = 1. Find a closed-form expression for T(n).
4.1. Solution
We'll solve this using GeneratingFunctions. Let F(z) = ∑ T(n)zn. Summing the recurrence times zn for all n gives
- F = zF + 2z²F + T(0) + z(T(1)-T(0)).
Here the T(0) term supplies the value of T(0)z0 on the left-hand side and the second term supplies the value of T(1)z1 (after compensating for the copy of zT(0) that gets thrown in by zF). Since T(1)-T(0) = 0, we can drop the second term, and get
- F = zF + 2z²F + 1.
Solving for F gives
- F = 1/(1-z-2z²).
We can factor 1-z-2z² as (1+z)(1-2z). Apply the cover-up method to split F into partial fractions as
![\[
F
= \frac{1}{(1+z)(1-2z)}
= \frac{1/(1-2(-1))}{1+z} + \frac{1/(1+1/2)}{1-2z}
= (1/3)\frac{1}{1+z} + (2/3) \frac{1}{1-2z}.
\]](/pinewiki/CS202/2007/Assignments/HW04/Solutions?action=AttachFile&do=get&target=latex_cf0e21246f83beeb0008fdedb636506bc0a98aa5_p1.png "\[
F
= \frac{1}{(1+z)(1-2z)}
= \frac{1/(1-2(-1))}{1+z} + \frac{1/(1+1/2)}{1-2z}
= (1/3)\frac{1}{1+z} + (2/3) \frac{1}{1-2z}.
\]")
From the formula for geometric series we can immediately read off that
T(n) = (1/3)(-1)n + (2/3)2n.
We can check this by computing a few values by hand (not required for your solution, but it's always a good idea):
n |
T(n) from recurrence |
T(n) from formula |
0 |
1 |
1/3 + 2/3 = 1 |
1 |
1 |
-1/3 + 4/3 = 1 |
2 |
3 |
1/3 + 8/3 = 3 |
3 |
5 |
-1/3 + 16/3 = 5 |
4 |
11 |
1/3 + 32/3 = 11 |
5 |
21 |
-1/3 + 64/3 = 21 |