I randomly encountered this post here, asking why this is true:

def subset(n, k): 
    if k == 0:
        return 1
    if n == k:
        return 1
        return subset(n-1, k-1) + subset(n-1, k)

Without reading the answer, I tried to understand the concept and it turned out not that complicated.

I wrote it as a math formula:

$${n \choose k} = {n-1 \choose k-1}+{n-1 \choose k}$$

This makes great sense when written down graphically on a piece of paper, but now I would like to know how to prove it mathematically.

Whould an induction proof be the correct one? As I only had 1 variable in my induction proofs before, this seems to be more complex.

My hypothesis:

  • Prove the above for ${0 \choose 0}$
  • Prove the above for ${n+1 \choose k}$
  • Prove the above for ${n \choose k+1}$
  • Prove the above for ${n+1 \choose k+1}$

Then, every possibility starting from ${0 \choose 0}$ would be covered. But imagine a formula having 5 variables, then this would imply at least $5^5$ proofs.

So is my approach correct? Is there a more elegant way of doing it?

Thank you!

  • 1
    $\begingroup$ You can do an induction proof on $n$ alone, where the statement about $n$ is "for all $k$, we have ${n\choose k}={n-1\choose k-1}+{n-1\choose k}$". The details of the proof ultimately depend on hwo you define $n\choose k$ in the first place. $\endgroup$ – Hagen von Eitzen Jan 4 '14 at 11:35
  • $\begingroup$ Ok, now you got me. How would one do it that way? I think that ${n \choose k}$ just has these restrictions: $n$ and $k$ are always both $\geq 0$ and $k \leq n$. Both, of course, are whole numbers. $\endgroup$ – Xiphias Jan 4 '14 at 11:37
  • $\begingroup$ In addition, none of the terms may be negative --- please watch the definition of the algorithm carefully for both special cases where there is 1 instead of the term. $\endgroup$ – Xiphias Jan 4 '14 at 11:43

Here's a more direct algebraic proof (note that the combinatorial proof provided in your link is, in my opinion, a lot more elegant). Given any positive integer $n$, choose any $k \in \{1,2,\ldots,n-1\}$. Then observe that: \begin{align*} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!(n - k)!} + \frac{(n-1)!}{k!(n - k - 1)!} \\ &= \frac{\color{red}{k}(n-1)!}{\color{red}{k}(k-1)!(n - k)!} + \frac{\color{red}{(n-k)}(n-1)!}{k!\color{red}{(n-k)}(n - k - 1)!} \\ &= \frac{k\color{blue}{(n-1)!} + (n-k)\color{blue}{(n-1)!}}{k!(n - k)!} \\ &= \frac{(k + (n - k))\color{blue}{(n-1)!}}{k!(n - k)!} \\ &= \frac{n(n-1)!}{k!(n - k)!} \\ &= \frac{n!}{k!(n - k)!} \\ &= \binom{n}{k} \\ \end{align*} as desired.

  • 1
    $\begingroup$ Thank you. Actually, I was so convinced of an induction proof that I forgot to "just" use simple math. I'd like to highlight that your use of colour makes it very readable. $\endgroup$ – Xiphias Jan 4 '14 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.