Derivation of a recursive binomial coefficient algorithm

Question

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?

Answer 1

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)!}.$$

Answer 2

The combinatorial interpretation makes these intuitive. See https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula.

Answer 3

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} $$