Here are the /Solutions.

# 1. Some binomial coefficients

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

# 2. More binomial coefficients

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

# 3. Still more binomial coefficients

Give a simple expression for

# 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_{1}x_{2}...x_{n} is a consecutive sequence of values x_{i}x_{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.