TAOCP 1.2.6 Exercise 59

Section 1.2.6: Binomial Coefficients

Exercise 59. [M25] A sequence of numbers $A_{nk}$ satisfies

$$ A_{n0}=1,\qquad A_{0k}=\delta_{0k},\qquad A_{nk}=A_{n-1,k}+A_{n-1,k-1}+\binom{n}{k}. $$

Find $A_{nk}$.

Verified: no
Solve time: -

---

Solution

Define

$$ B_{nk}=A_{nk}-\binom{n+1}{k}. $$

Then

$$ B_{n0}=A_{n0}-\binom{n+1}{0}=1-1=0, $$

and

$$ B_{0k}=A_{0k}-\binom{1}{k} =\delta_{0k}-\binom{1}{k}=0 \qquad (k\ge0), $$

since

$$ \binom{1}{0}=1,\qquad \binom{1}{1}=1,\qquad \binom{1}{k}=0\quad(k>1). $$

Using the addition formula (9),

$$ \binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}. $$

Hence

\begin{align*}

B_{nk}

&=A_{nk}-\binom{n+1}{k} \

&=A_{n-1,k}+A_{n-1,k-1}+\binom{n}{k}

-\binom{n}{k}-\binom{n}{k-1} \

&=\bigl(A_{n-1,k}-\binom{n}{k}\bigr)

+\bigl(A_{n-1,k-1}-\binom{n}{k-1}\bigr) \

&=B_{n-1,k}+B_{n-1,k-1}.

\end{align*}

Thus $B_{nk}$ satisfies Pascal's recurrence,

$$ B_{nk}=B_{n-1,k}+B_{n-1,k-1}, $$

with boundary conditions

$$ B_{n0}=0,\qquad B_{0k}=0. $$

We prove by induction on $n$ that

$$ B_{nk}=0 \qquad\text{for all }n,k\ge0. $$

The case $n=0$ is already established. Assume that

$$ B_{n-1,j}=0 \qquad\text{for all }j\ge0. $$

Then

$$ B_{nk}=B_{n-1,k}+B_{n-1,k-1}=0+0=0. $$

Therefore $B_{nk}=0$ for all $n,k$.

Consequently,

$$ A_{nk}=\binom{n+1}{k}. $$

Verification:

\begin{align*}

A_{n-1,k}+A_{n-1,k-1}+\binom{n}{k}

&=\binom{n}{k}+\binom{n}{k-1}+\binom{n}{k} \

&=\binom{n+1}{k}+\binom{n}{k} \

&=A_{nk}.

\end{align*}

Also,

$$ A_{n0}=\binom{n+1}{0}=1, $$

and

$$ A_{0k}=\binom{1}{k}=\delta_{0k}. $$

Therefore the required sequence is

$$ \boxed{A_{nk}=\binom{n+1}{k}}. $$