\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions -- Problem Set 3}
\centerline{February 21, 2005}
\bigskip
\noindent
Chapter 5/3.  The problem says find the relation between the sums
of these diagonals in Pascal's triangle.  Let $d_n$ be
the sum of the entries starting with the first entry (at left)
on row $n$, then the second entry on row $n-1$, etc:
$$d_n = \sum_{k=0}^{\lfloor k/2 \rfloor} {n-k \choose k} = {n\choose 0} + {n - 1\choose 1} + {n - 2\choose 2} + \cdots \leqno(1)$$
Computing the first few of these, we see
$$d_0 = 1, d_1 = 1, d_2 = 2, d_3 = 3, d_4 = 5, d_5 = 8, d_6 = 13, \ldots$$
From this ``data'', since each number (after the first two, of course) is the 
sum of the previous two, it would appear that $d_n$ is the sequence of 
Fibonacci numbers.  {\it No mathematical assertion like that is 
complete without a proof, though!!}
\bigskip
\noindent
Using (1), we will show that $d_n$ satisfies the recurrence relation 
of the Fibonacci numbers:  $d_n = d_{n-1} + d_{n-2}$ for all $n \ge 2$.
(Then, since $d_0 = d_1 = 1$, we have $d_n = n$th Fibonacci number for
all $n$.)  Start on the right hand side of the equation we want to show,
use (1), and regroup terms to apply the Pascal's triangle identity
(noting that ${n-1\choose -1} = 0$):
$$\eqalign{
d_{n-1} + d_{n-2} &= 
\left({n-1\choose 0} + {n - 2\choose 1} + {n - 3\choose 2} + \cdots\ \right)\cr
& \qquad +
\left({n-2\choose 0} + {n - 3\choose 1} + {n - 4\choose 2} + \cdots\ \right)\cr
&= \left({n-1\choose 0} + {n-1\choose -1}\right) + 
   \left({n-2\choose 1} + {n-2\choose 0}\right) \cr
&\qquad + \left({n-3\choose 2} + {n-3\choose 1}\right) + \cdots\cr
&= {n\choose 0} + {n-1\choose 1} + {n-2\choose 2} + \cdots\cr
&= d_n.\cr}$$
Hence $d_n = d_{n-1} + d_{n-2}$ for all $n \ge 2$, which is what we
wanted to show.
\bigskip
\noindent
Chapter 5/13.  This is an interesting problem because there are 
two somewhat different approaches to showing the desired identity.

\bigskip
\noindent
Method 1:  Regroup terms and use the Pascal triangle identity repeatedly:
$$\eqalign{
&{n \choose k} + 3 {n \choose k-1} + 3{n \choose k-2} + {n \choose k-3}\cr
&=\left({n \choose k} + {n \choose k-1}\right) + 
2\left({n \choose k-1} + {n \choose k-2}\right) + 
\left({n \choose k-2} + {n \choose k-3}\right)\cr
&= {n+1\choose k} + 2{n+1\choose k-1} + {n+1\choose k-2}\cr
&= \left({n+1\choose k} + {n+1\choose k-1}\right) + 
\left({n+1\choose k-1} + {n+1\choose k-2}\right)\cr 
&= {n+2\choose k} + {n+2\choose k-1}\cr
&={n+3\choose k}\cr}$$

\bigskip
\noindent
Method 2:  Notice that the coefficients $1,3,3,1$ are one
of the rows of Pascal's triangle.  So the sum can be rewritten
as 
$${3\choose 0}{n \choose k} + {3\choose 1}{n \choose k-1} + 
{3\choose 2}{n \choose k-2} + {3\choose 3}{n \choose k-3}$$
Since in this sum the upper indices are the same in all terms
and the lower indices sum to $k$ in each product, the Vandermonde
Convolution identity applies.  We have that the given sum is 
$$ \sum_{\ell} {3\choose \ell}{n \choose k - \ell} = {3 + n \choose k}$$
(Note that $\ell = 0,1,2,3$ are the only values of 
$\ell$ where ${3\choose \ell} \ne 0$.)
\bigskip
\noindent
Chapter 5/28.  Recall that in class we showed
$$n2^{n-1} = \sum_{k=1}^n k {n \choose k}\leqno(2)$$
by a combinatorial argument counting the number of ways
to select a committee (of any size $\ge 1$)  with a designated chair
from a total pool of $n$ candidates.  Similarly, we can count
the number of ways to 
select a committee with a designated
chair and a designated secretary (not the same as the chair). On the 
one hand, we can select the committee first (${n \choose k}$
committees of size $k$, and all $k \ge 1$), then select the chair and 
secretary from the membership of the committee.
Or, we can select the chair and secretary from the whole
pool, then fill out the rest of the membership.  The first way
gives the right side, and the second way gives the left in
the following equation:
$$n(n-1)2^{n-2} = \sum_{k=1}^n k(k-1){n \choose k}\leqno(3)$$
Hence if we add corresponding sides of (2) and (3) and simplify, we get
$$\eqalign{n2^{n-1} + n(n-1)2^{n-2} &= \sum_{k=1}^n k(k-1){n \choose k} + \sum_{k=1}^n k {n \choose k}\cr
\Rightarrow n(n+1)2^{n-2} &=\sum_{k=1}^n (k^2 - k + k) {n\choose k}\cr
&= \sum_{k=1}^n k^2 {n\choose k}\cr}\leqno(4)$$
which is what we want.

As a number of people saw, you can also give a combinatorial
interpretation for the sum of (2) and (3).  Namely, if you 
allow {\it the chair and the secretary to be the same person}, then
the $\sum_{k=1}^n k^2 {n\choose k}$ counts the total number of ways to 
choose a committee with two distinguished members (possibly the same
person).
Then the sum on the left of (4) takes into account the two 
cases where the chair and secretary are the same, and when 
they are distinct.

\bye

