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 pdfTeXk, Version 3.1415926-1.40.9 (Web2C 7.5.7)
 %&-line parsing enabled.
entering extended mode
(./latex_9c843461109b74788562f708c6d5e918fbb72e48_p.tex
LaTeX2e <2005/12/01>
Babel <v3.8l> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, german-x-2008-06-18, ngerman-x-2008-06-18, ancientgreek, ibycus, ar
abic, basque, bulgarian, catalan, pinyin, coptic, croatian, czech, danish, dutc
h, esperanto, estonian, farsi, finnish, french, galician, german, ngerman, mono
greek, greek, hungarian, icelandic, indonesian, interlingua, irish, italian, la
tin, lithuanian, mongolian, mongolian2a, bokmal, nynorsk, polish, portuguese, r
omanian, russian, sanskrit, serbian, slovak, slovenian, spanish, swedish, turki
sh, ukenglish, ukrainian, uppersorbian, welsh, loaded.
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/size12.clo))
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/inputenc.sty
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/utf8.def
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/t1enc.dfu)
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/ot1enc.dfu)
(/usr/local/texlive/2008/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 pdfTeXk, Version 3.1415926-1.40.9 (Web2C 7.5.7)
 %&-line parsing enabled.
entering extended mode
(./latex_7e1ab53e13accb7da7d6ed4fc662c2a9abc89132_p.tex
LaTeX2e <2005/12/01>
Babel <v3.8l> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, german-x-2008-06-18, ngerman-x-2008-06-18, ancientgreek, ibycus, ar
abic, basque, bulgarian, catalan, pinyin, coptic, croatian, czech, danish, dutc
h, esperanto, estonian, farsi, finnish, french, galician, german, ngerman, mono
greek, greek, hungarian, icelandic, indonesian, interlingua, irish, italian, la
tin, lithuanian, mongolian, mongolian2a, bokmal, nynorsk, polish, portuguese, r
omanian, russian, sanskrit, serbian, slovak, slovenian, spanish, swedish, turki
sh, ukenglish, ukrainian, uppersorbian, welsh, loaded.
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/size12.clo))
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/inputenc.sty
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/utf8.def
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/t1enc.dfu)
(/usr/local/texlive/2008/texmf-dist/tex/latex/base/ot1enc.dfu)
(/usr/local/texlive/2008/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).

CS202/2005/Assignments/HW04/Solutions (last edited 2007-12-25 23:42:01 by localhost)