# Derivation of a recursive binomial coefficient algorithm

I am working through a Haskell book and I see that the binomial coefficients formula

$$\binom{n}{k} = \frac {n!}{k! (n - k)!}$$

is expressible as recurrence relationships

\begin{align} \binom{n}{k} &= \binom{n - 1}{k - 1} \frac{n}{k} \quad \text{for} \; n \gt 0 \\ \binom{n}{0} &= 1 \end{align}

and as

\begin{align} \binom{n}{k} &= \binom{n - 1}{k - 1} + \binom{n - 1}{k} \\ \binom{n}{0} &= 1 \end{align}

My question is how were these derived from the original formula above? Is there a treatment, a proof anywhere of how these were derived that I could see?

Update

Yes, the classic algebra assignment is to take the recurrence relation and simplify it back to the original as a proof that the recursive version is indeed the same as the original

$$\binom{n}{k} = \frac {n!}{k! (n - k)!} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$$

Instructive, but I would like to know how the recursive version was derived in the first place. I assume that there is was no systematic way, that it was just a guess -- or perhaps some much deeper numerical analysis issue?

• Your first relation is wrong.
– user65203
Feb 6, 2021 at 16:16
• Got it. Messed up with MathJax Feb 6, 2021 at 16:37

We have identity $$n! = n\cdot(n-1)!$$ So for the first recurrence, \begin{align} \frac {n!}{k! (n - k)!} &= \frac{n}{k}\cdot\frac{(n-1)!}{(k-1)!(n-k)!} \\ &= \frac{n}{k}\cdot\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} \\ &= \frac{n}{k}\binom{n-1}{k-1} \end{align}
Reducing to the common denominator, $$\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{(n-k+k)(n-1)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}.$$