TAOCP 1.2.6 Exercise 6

Section 1.2.6: Binomial Coefficients

Exercise 6. [10] Pascal's triangle (Table 1) can be extended in all directions by use of the addition formula, Eq. (9). Find the three rows that go on top of Table 1 (i.e., for $r=-1$, $-2$, and $-3$).

Verified: yes
Solve time: 41s

Using Eq. (9),

$$ \binom{r}{k}=\binom{r-1}{k}+\binom{r-1}{k-1}, $$

the rows above Table 1 are determined uniquely by working upward. Since every entry equals the sum of the two entries above it, an upper entry is obtained by subtraction. Beginning with the row for $r=0$,

$$ 1,\ 0,\ 0,\ 0,\ 0,\ldots $$

the row for $r=-1$ must satisfy

$$ 1=\binom{-1}{0},\qquad 0=\binom{-1}{1}+\binom{-1}{0}, $$

hence $\binom{-1}{1}=-1$; continuing in the same way gives alternating signs. Repeating the process for $r=-2$ and $r=-3$ yields

$$ r=-1:\qquad 1,\ -1,\ 1,\ -1,\ 1,\ -1,\ 1,\ldots $$

$$ r=-2:\qquad 1,\ -2,\ 3,\ -4,\ 5,\ -6,\ 7,\ldots $$

$$ r=-3:\qquad 1,\ -3,\ 6,\ -10,\ 15,\ -21,\ 28,\ldots $$

Equivalently, by Eq. (3),

$$ \binom{-1}{k}=(-1)^k,\qquad \binom{-2}{k}=(-1)^k(k+1),\qquad \binom{-3}{k}=(-1)^k\binom{k+2}{2}, $$

which agrees with the rows above. Thus the three rows are

$$ \boxed{ \begin{array}{rcccccccc} r=-1:&1&-1&1&-1&1&-1&\cdots\ r=-2:&1&-2&3&-4&5&-6&\cdots\ r=-3:&1&-3&6&-10&15&-21&\cdots \end{array}} $$