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.
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?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?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.
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?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}.
\]")
Note: Typo in the identity corrected 2007-10-08; previous version had the wrong operation on the right-hand side.
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).