# 1. Some binomial coefficients

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

## 1.1. Solution

There are several ways to prove this. The easiest is perhaps by induction on n. First observe that

since either k = 0 and both binomial coefficients are 1 or k > 0 and both are 0.

For larger n, we have

latex error! exitcode was 1 (signal 0), transscript follows: This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) entering extended mode (./latex_9c843461109b74788562f708c6d5e918fbb72e48_p.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 78 languages loaded. (/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo)) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty (/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def (/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu))) No file latex_9c843461109b74788562f708c6d5e918fbb72e48_p.aux. ! LaTeX Error: Bad math environment delimiter. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.8 \[ \sum_{m=0}^{n} {m \choose k} [1] (./latex_9c843461109b74788562f708c6d5e918fbb72e48_p.aux) ) (see the transcript file for additional information) Output written on latex_9c843461109b74788562f708c6d5e918fbb72e48_p.dvi (1 page, 964 bytes). Transcript written on latex_9c843461109b74788562f708c6d5e918fbb72e48_p.log.

(Here the second-to-last step uses the induction hypothesis and the last uses Pascal's identity.)

# 2. More binomial coefficients

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

## 2.1. Solution

Observe that the left-hand side counts the number of ways, starting with a set S of n elements, to choose a subset A of S with k elements and then choose a further subset B of A with m elements. On the right-hand side, we first choose B (a subset of S with m elements) and then choose the remaining k-m elements of A from the remaining n-m elements of S. Since both methods give us the same chain of subsets A, B, and S, we have a combinatorial proof of the identity.

(It's also possible to do this directly by expanding the binomial coefficients into factorials, but it's messy.)

# 3. Still more binomial coefficients

Give a simple expression for

## 3.1. Solution

This is a job for generating functions!

Compute:

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

## 4.1. Solution

Do the generating-function trick of multiplying by z^{n} and adding for all n:

Solve for F(z) to get

latex error! exitcode was 1 (signal 0), transscript follows: This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013) entering extended mode (./latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.tex LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 78 languages loaded. (/usr/local/texlive/2013/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/local/texlive/2013/texmf-dist/tex/latex/base/size12.clo)) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/inputenc.sty (/usr/local/texlive/2013/texmf-dist/tex/latex/base/utf8.def (/usr/local/texlive/2013/texmf-dist/tex/latex/base/t1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/ot1enc.dfu) (/usr/local/texlive/2013/texmf-dist/tex/latex/base/omsenc.dfu))) No file latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.aux. ! LaTeX Error: \begin{eqnarray*} on input line 7 ended by \end{document}. See the LaTeX manual or LaTeX Companion for explanation. Type H <return> for immediate help. ... l.11 \end{document} ! Missing $ inserted. <inserted text> $ l.11 \end{document} ! Missing } inserted. <inserted text> } l.11 \end{document} ! Missing } inserted. <inserted text> } l.11 \end{document} ! Missing \cr inserted. <inserted text> \cr l.11 \end{document} ! Missing { inserted. <inserted text> { l.11 \end{document} ! Missing $ inserted. <inserted text> $ l.11 \end{document} ! Missing $$ inserted. <to be read again> \par l.11 \end{document} [1] (./latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.aux) ) (\end occurred inside a group at level 1) ### semi simple group (level 1) entered at line 7 (\begingroup) ### bottom level (see the transcript file for additional information) Output written on latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.dvi (1 page, 688 bytes). Transcript written on latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.log.

and finally we can read off the coefficients T(n) = (3/4)*3^{n} + (1/4)*(-1)^{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.

## 5.1. Solution

- 1 (the all-1's string).
n+1. Any string that doesn't contain 01 must be of the form 1

^{k}0^{n-k}, since after the first 0 we can only have more 0's. The number of 1's can range from 0 to n, giving n+1 possibilities.Let's partition the set of strings that don't contain 00 into those that are empty, those that start with 0 and those that start with 1. Let T

_{i}(n) be the number of length-n strings that start with i. Then T(0) = 1 and T(n) = T_{0}(n) + T_{1}(n) when n > 0. But T_{0}(n) = T_{1}(n-1) for n > 1 since after the initial 0 we must continue with a 1 followed by a string that contains no 00's; for n = 1 we have the special case T_{0}(1) = 1. For T_{1}we have T_{1}(n) = T(n-1) since we can continue with either 0 or 1. We also have T_{0}(0) = T_{1}(0) = 0 since a zero-length string doesn't start with either 0 or 1.

Let's build up a table of values and see if we recognize the sequence:

n |
T |
T |
T(n) |

0 |
0 |
0 |
1 |

1 |
1 |
1 |
2 |

2 |
1 |
2 |
3 |

3 |
2 |
3 |
5 |

4 |
3 |
5 |
8 |

5 |
5 |
8 |
13 |

By now the pattern is pretty well established: for large n, T(n) = T_{0}(n) + T_{1}(n) = T_{1}(n-1) + T(n-1) = T(n-2) + T(n-1), and the numbers in the last column look suspiciously like the Fibonacci_numbers Fib(n+2). To prove this, observe that T(0) = 1 = Fib(2) and T(1) = 2 = Fib(3), and for larger n the recurrence holds as discussed above.

We could stop here, arguing that Fib(n+2) is a pretty well-known sequence with a simple formula, or we could try to derive one using generating functions. (Looking in BiggsBook doesn't help us, although it is a common enough example that we could probably find the formula on the web somewhere.)

So if we have to build a generating function, perhaps we should do so directly. Summing up our various recurrences we have

From this solve for F to get F(z) = (1+z)/(1-z-z^{2}). Extracting coefficients is the usual exercise in partial fraction expansion (which we'll omit in these solutions but which you should know how to do).