# 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}.

## 1.1. Solution

Base case: k=0, and we have d

^{0}/dz^{0}(1+z)^{n}= (1+z)^{n}= n_{(0)}(1+z)^{n-0}. Induction step: Suppose d^{k-1}/dz^{k-1}(1+z)^{n}= n_{(k-1)}(1+z)^{n-k+1}. Then d^{k}/dz^{k}(1+z)^{n}= d/dz (d^{k-1}/dz^{k-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 a

_{k}= (1/k!) d^{k}/dz^{k}(1+z)^{n}|_{z=0}= (1/k!) n_{(k)}(1+z)^{n-k}|_{z=0}= n_{(k)}1^{n-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^{-k}y^{k}. Now multiply both sides by x^{n}to get x^{n}(1+y/x)^{n}= (x+y)^{n}= ∑ (n_{(k)}/k!) x^{n-k}y^{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.

## 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) = ∑ 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

## 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)z^{n}. Summing the recurrence times z^{n} 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)z^{0} on the left-hand side and the second term supplies the value of T(1)z^{1} (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

From the formula for geometric series we can immediately read off that

T(n) = (1/3)(-1)

^{n}+ (2/3)2^{n}.

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 |