0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Your first relation is wrong. $\endgroup$
    – user65203
    Feb 6, 2021 at 16:16
  • $\begingroup$ Got it. Messed up with MathJax $\endgroup$
    – 147pm
    Feb 6, 2021 at 16:37

3 Answers 3

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Yes, I think I understand how the second one submits to regular algebra. What about the first one? $\endgroup$
    – 147pm
    Feb 6, 2021 at 16:45
  • 1
    $\begingroup$ @147pm: try, you can do it. $\endgroup$
    – user65203
    Feb 6, 2021 at 16:52
  • $\begingroup$ See my update, please. $\endgroup$
    – 147pm
    Feb 8, 2021 at 5:19
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .