PineWikiHere 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}.\]](/pinewiki/CS202/2005/Assignments/HW04?action=AttachFile&do=get&target=latex_b7bccb06558f3623349ce00e0d0acaa21b723f6c_p1.png "\[\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}.\]](/pinewiki/CS202/2005/Assignments/HW04?action=AttachFile&do=get&target=latex_6ef84b276fba267a3faff883e5d28d6ac6807f94_p1.png "\[{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}.\]](/pinewiki/CS202/2005/Assignments/HW04?action=AttachFile&do=get&target=latex_af091f1e5207a132ece058cf827a89e54f7ed5f7_p1.png "\[\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 x1x2...xn is a consecutive sequence of values xixi+1...xi+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 Fn, you can stop there without trying to find a simpler expression.
