[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Solutions

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.

  1. Prove by induction on k that dk/dzk (1+z)n = n(k) (1+z)n-k for all k in ℕ.

  2. Use this fact to show that if (1+z)n = ∑ akzk, then ak = n(k)/k!.

  3. 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}.
\]

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}.
\]

  1. Give a combinatorial interpretation of TVI.
  2. Prove TVI is true.

3. Sequence differences

  1. 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.

  2. Prove the identity

\[
{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).


2014-06-17 11:57