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.

Here are the /Solutions.

1. Some binomial coefficients

Prove that, for all non-negative integers n and k,

$\sum_{m=0}^{n} {m \choose k} = {n+1 \choose k+1}.$

2. More binomial coefficients

Prove that, for all non-negative integers n, m, and k,

${n \choose k}{k \choose m} = {n \choose m}{n - m \choose k - m}.$

3. Still more binomial coefficients

Give a simple expression for

$\sum_{k=0}^n k^2 {n \choose k}.$

4. 1, 2, 3

Let

T(0) = 1, T(1) = 2, and
T(n) = 2T(n-1) + 3T(n-2) when n > 1.

Determine a simple non-recursive formula for T(n).

5. Forbidden substrings

A substring of a sequence x₁x₂...x_n is a consecutive sequence of values x_ix_i+1...x_i+k that appears in the original sequence. So for example 010 is a substring of 00100 but not of 01100. An n-bit string is a sequence of n bits, where a bit is either 0 or 1.

Give the simplest expression you can as a function of n for

The number of n-bit strings that do not contain 0 as a substring.
The number of n-bit strings that do not contain 01 as a substring.
The number of n-bit strings that do not contain 00 as a substring.

Hint: If you can express one or more of these quantities directly in terms of the FibonacciNumbers F_n, you can stop there without trying to find a simpler expression.