Exercise 12.4.1

Prove equation (12.3).

$$ \sum_{i=0}^{n-1} \binom{i+3}{3} = \binom{n+3}{4} $$

Let's use induction here.

We'll start with $n=2$ in the base, as it will illustrate the step more clearly:

$$ \sum_{i=0}^{1} \binom{i+3}{3} = \binom{3}{3} + \binom{4!}{3!} = \frac{3!}{3!} + \binom{4!}{3!} = \frac{3 \cdot 2 \cdot 1}{3!} + \frac{4 \cdot 3 \cdot 2}{3!} = \frac{(4 + 1) \cdot 3 \cdot 2 \cdot 1}{3!} = \frac{4 \cdot 5 \cdot 3 \cdot 2}{4 \cdot 3!} = \frac{5!}{4! \cdot 1!} = \binom{5}{4} = \binom{2 + 3}{4} $$

For the step, we do this:

$$ \begin{aligned} \sum_{i=0}^{n} \binom{i+3}{3} &= \sum_{i=0}^{n} \binom{i+3}{3} \\ &= \sum_{i=0}^{n-1} \binom{i+3}{3} + \binom{n+3}{3} \\ &= \binom{n+2}{4} + \binom{n+3}{3} \\ &= \frac{(n+3)(n+2)(n+1)n}{4!} + \frac{(n+3)(n+2)(n+1)}{3!} \cdot \frac{4}{4} \\ &= \frac{(n+3)(n+2)(n+1)(n + 4)}{4!} \\ &= \binom{n+4}{4} \end{aligned} $$