Mathematics 357 – Combinatorics Selected Solutions – Problem Set 3 February 21, 2005

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:

(1)  d_{n} = ∑_{k=0}^{⌊k/2⌋} \binom{n − k}{k} = \binom{n}{0} + \binom{n − 1}{1} + \binom{n − 2}{2} + ⋯

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, …

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. No mathematical assertion like that is complete without a proof, though!!

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 ≥ 2. (Then, since d_{0} = d_{1} = 1, we have d_{n} = nth 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 \binom{n−1}{−1} = 0):

d_{n−1} + d_{n−2} = (\binom{n − 1}{0} + \binom{n − 2}{1} + \binom{n − 3}{2} + ⋯)

+ (\binom{n − 2}{0} + \binom{n − 3}{1} + \binom{n − 4}{2} + ⋯)

= (\binom{n − 1}{0} + \binom{n − 1}{−1}) + (\binom{n − 2}{1} + \binom{n − 2}{0})

+ (\binom{n − 3}{2} + \binom{n − 3}{1}) + ⋯

= \binom{n}{0} + \binom{n − 1}{1} + \binom{n − 2}{2} + ⋯

= d_{n}.

Hence d_{n} = d_{n−1} + d_{n−2} for all n ≥ 2, which is what we wanted to show.

Chapter 5/13. This is an interesting problem because there are two somewhat different approaches to showing the desired identity.

Method 1: Regroup terms and use the Pascal triangle identity repeatedly:

\binom{n}{k} + 3\binom{n}{k − 1} + 3\binom{n}{k − 2} + \binom{n}{k − 3}

= (\binom{n}{k} + \binom{n}{k − 1}) + 2 (\binom{n}{k − 1} + \binom{n}{k − 2}) + (\binom{n}{k − 2} + \binom{n}{k − 3})

= \binom{n + 1}{k} + 2\binom{n + 1}{k − 1} + \binom{n + 1}{k − 2}

= (\binom{n + 1}{k} + \binom{n + 1}{k − 1}) + (\binom{n + 1}{k − 1} + \binom{n + 1}{k − 2})

= \binom{n + 2}{k} + \binom{n + 2}{k − 1}

= \binom{n + 3}{k}

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

\binom{3}{0}\binom{n}{k} + \binom{3}{1}\binom{n}{k − 1} + \binom{3}{2}\binom{n}{k − 2} + \binom{3}{3}\binom{n}{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

∑_{ℓ} \binom{3}{ℓ}\binom{n}{k − ℓ} = \binom{3 + n}{k}

(Note that ℓ = 0, 1, 2, 3 are the only values of ℓ where \binom{3}{ℓ} ≠ 0.)

Chapter 5/28. Recall that in class we showed

(2)  n2^{n−1} = ∑_{k=1}^{n} k\binom{n}{k}

by a combinatorial argument counting the number of ways to select a committee (of any size ≥ 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 (\binom{n}{k} committees of size k, and all k ≥ 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:

(3)  n(n − 1)2^{n−2} = ∑_{k=1}^{n} k(k − 1)\binom{n}{k}

Hence if we add corresponding sides of (2) and (3) and simplify, we get

(4)  \begin{aligned}n2^{n−1} + n(n − 1)2^{n−2} & = ∑_{k=1}^{n} k(k − 1)\binom{n}{k} + ∑_{k=1}^{n} k\binom{n}{k} \\ ⇒ n(n + 1)2^{n−2} & = ∑_{k=1}^{n}(k^{2} − k + k)\binom{n}{k} \\ & = ∑_{k=1}^{n} k^{2}\binom{n}{k} \end{aligned}

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 the chair and the secretary to be the same person, then the ∑_{k=1}^{n} k^{2}\binom{n}{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.