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.

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}.$

1.1. Solution

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

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

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,

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

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

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

3.1. Solution

This is a job for generating functions!

Compute:

$\begin{eqnarray*} \sum_{k=0}^{n} {n \choose k} z^k &=& (1+z)^n. \\ \sum_{k=0}^{n} k {n \choose k} z^k &=& z \frac{d}{dz} (1+z)^n \\ &=& nz(1+z)^{n-1}.\\ \sum_{k=0}^n k^2 {n \choose k} z^k &=& z \frac{d}{dz} nz(1+z)^{n-1} \\ &=& n(n-1)z^2(1+z)^{n-2} + nz(1+z)^{n-1}. \\ \sum_{k=0}^n k^2 {n \choose k} &=& n(n-1)(1+1)^{n-2} + n(1+1)^{n-1} \\ &=& 2^{n-2}\left(n(n-1) + 2n\right) \\ &=& 2^{n-2}(n^2 + n). \end{eqnarray*}$

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ⁿ and adding for all n:

$\begin{eqnarray*} T(0) + T(1)z + \sum_{n=2}^{\infty} T(n)z^n &=& 1 + 2z + \sum_{n=2}^{\infty} \left(2T(n-1)z^n + 3T(n-2)z^n\right) \\ \sum_{n=0}^{\infty} T(n) z^n &=& 1 + 2z + \sum_{n=1}^{\infty} 2T(n) z^{n+1} + \sum_{n=0}^{\infty} 3T(n) z^{n+2} \\ F(z) &=& 1 + 2z + 2z(F(z) - T(0)) + 3z^2(F(z)) \\ &=& 1 + 2z + 2zF(z) - 2z + 3z^2F(z) \\ &=& 1 + 2zF(z) + 3z^2F(z). \end{eqnarray*}$

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ⁿ + (1/4)*(-1)ⁿ.

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.

5.1. Solution

1 (the all-1's string).
n+1. Any string that doesn't contain 01 must be of the form 1^k0^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₀(n) + T₁(n) when n > 0. But T₀(n) = T₁(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₀(1) = 1. For T₁ we have T₁(n) = T(n-1) since we can continue with either 0 or 1. We also have T₀(0) = T₁(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₀(n)	T₁(n)	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₀(n) + T₁(n) = T₁(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

$\begin{eqnarray*} F_0 &=& z + zF_1 \\ F_1 &=& zF \\ F &=& 1 + F_0 + F_1 \\ &=& 1 + z + zF_1 + F_1 \\ &=& 1 + z + z^2 F + zF. \end{eqnarray*}$

From this solve for F to get F(z) = (1+z)/(1-z-z²). 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).