TAOCP 1.2.6 Exercise 24

Section 1.2.6: Binomial Coefficients

Exercise 24. [M15] Explain why the results of the previous two exercises combine to give a proof of Eq. (26).

Verified: no
Solve time: 1m30s

Solution

Exercise 22 proves Eq. (26) for all quadruples $(r,s,t,n)$ satisfying

$$ s=(n-1)r+nt. $$

Exercise 23 proves the following induction step:

If Eq. (26) holds for $(r,s,t,n)$ and for $(r,s-t,t,n-1)$, then it also holds for $(r,s+1,t,n)$.

Fix $r,t,n$, and define

$$ s_0=(n-1)r+nt. $$

By Exercise 22, Eq. (26) is true when $s=s_0$.

Apply Exercise 23 with $s=s_0$. Since Eq. (26) holds for $(r,s_0,t,n)$, and since the second hypothesis concerns $(r,s_0-t,t,n-1)$, whose corresponding special value is

$$ (n-2)r+(n-1)t=s_0-t, $$

Exercise 22 also guarantees the second hypothesis. Hence Eq. (26) holds for $(r,s_0+1,t,n)$.

Now repeat the argument with $s=s_0+1$, then with $s=s_0+2$, and so on. By induction, Eq. (26) holds for all integers

$$ s\ge s_0=(n-1)r+nt. $$

This is precisely the range of validity required for Eq. (26). Therefore Exercises 22 and 23 together constitute a proof of Eq. (26).

This completes the proof.

∎