1

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
    else:
        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!

Community
  • 1
Xiphias
  • 709
  • 1
    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. – Hagen von Eitzen Jan 04 '14 at 11:35
  • 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. – Xiphias Jan 04 '14 at 11:37
  • 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. – Xiphias Jan 04 '14 at 11:43

1 Answers1

1

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.

Adriano
  • 41,576
  • 1
    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. – Xiphias Jan 04 '14 at 12:45