# Is the approach to proving this expression for an n-choose-k algorithm correct?

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!

• 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 4 '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 4 '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 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.