# 1. Prove the binomial theorem

Recall that if F(z) = ∑ a_{k}z^{k}, then we can extract a_{k} by differentiating F k times, dividing by k!, and setting the result to 0, i.e. a_{k} = (1/k!) d^{k}/dz^{k} F(z) |_{z=0}.

Prove by induction on k that d

^{k}/dz^{k}(1+z)^{n}= n_{(k)}(1+z)^{n-k}for all k in ℕ.Use this fact to show that if (1+z)

^{n}= ∑ a_{k}z^{k}, then a_{k}= n_{(k)}/k!.Use the preceding to prove that (x+y)

^{n}= ∑ (n_{(k)}/k!) x^{k}y^{n-k}.

# 2. A triple identity

Recall Vandermonde's identity (see BinomialCoefficients):

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:

- Give a combinatorial interpretation of TVI.
- Prove TVI is true.

# 3. Sequence differences

Suppose you have a generating function F(z) = ∑ a

_{n}z^{n}. Write an expression in terms of F for the generating function G of the sequence given by the rule b_{n}= a_{n}-a_{n-1}.- Prove the identity

**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).