Why is ${{n+1}\choose{k}}={{n}\choose{k-1}}+{{n}\choose{k}}$?

Question

My teacher showed us a proof by induction for this equation for $n\in\mathbb{N}$:

$$\sum\limits_{k=0}^n{{n}\choose{k}} = 2^n$$

In the first step, this sum is rewritten using ${{n+1}\choose{k}}={{n}\choose{k-1}}+{{n}\choose{k}}$.

However, he doesn't explain why this would be - and since he just introduced binomials coefficients, I assume it's something trivial, which I just don't see. I can't figure out why this would hold though.

I tried rewriting the binomial coefficients with ${{n}\choose{k}}=\frac{n!}{k!\cdot(n-k)!}$ when $n,k\in\mathbb{N}$ and $n\geq k$:

$${{n+1}\choose{k}}=\frac{(n+1)!}{k!\cdot(n+1-k)!}$$

$${{n}\choose{k-1}}=\frac{n!}{(k-1)!\cdot(n-k+1)!}$$

$${{n}\choose{k}}=\frac{n!}{k!\cdot(n-k)!}$$

But I can't prove:

$$\frac{(n+1)!}{k!\cdot(n+1-k)!} \stackrel{?}{=} \frac{n!}{(k-1)!\cdot(n-k+1)!} + \frac{n!}{k!\cdot(n-k)!}$$

Am I on the right track? Is there a basic idea behind this equation which makes you see it easily?

Answer 1

I can give you an other way of proving this without any calculus.

What is ${{n}\choose{k}}$? This is the number of ways to choose k elements among n ones, without specifying an order.

So let's have the set: A=$(a_1...a_n)$ n elements ( tennis balls per say). Let's look at one particularly: $a_i$ because it is the only red ball of the set.

The number of ways to choose k elements in A is the number of ways to choose k elements with $a_i$ in it, plus the number of ways to choose k elements without $a_i$.

For the first, since you know that among the k elements $a_i$ has to be present you can choose k-1 elements among n-1 elements ($a_i$ has already been chosen so your set is diminished of one ball, that gives n-1 elements left). This gives ${{n-1}\choose{k-1}}$

Likewise, for the second you know that $a_i$ is not part of your choosing so you have to choose k elements among n-1 elements, that is ${{n-1}\choose{k}}$

So you get the equality : ${{n}\choose{k}} = {{n-1}\choose{k-1}} + {{n-1}\choose{k}}$

Answer 2

Algebra: note that $\;r!=r(r-1)!\;,\;\;\frac{r!}r=(r-1)!\;$ , and also correcting your equalities we have

$$\binom n{k-1}=\frac{n!}{(k-1)!(n-k+1)!}\;,\;\;\binom nk=\frac{n!}{k!(n-k)!}$$

so that we actually should have on the RHS of your last equality

$$\frac{n!}{(k-1)!\cdot(n-k+1)!} + \frac{n!}{k!\cdot(n-k)!}=n!\frac{k+n-k+1}{k!(n-k+1)!}=$$

$$=\frac{n!(n+1)}{k!(n-k+1)!}=\binom{n+1}{k}$$

Answer 3

$$\dfrac{1}{k}+\dfrac{1}{n-k+1}=\dfrac{n+1}{k(n-k+1)}\\ \left(\dfrac{n!}{(k-1)!(n-k)!}\right)\left(\dfrac{1}{k}+\dfrac{1}{n-k+1}\right)=\left(\dfrac{n!}{(k-1)!(n-k)!}\right)\left(\dfrac{n+1}{k(n-k+1)}\right)\\ \displaystyle\binom{n}{k}+\displaystyle\binom{n}{k-1}=\displaystyle\binom{n+1}{k}$$

Answer 4

you mismatched:

you must verify

$$\frac{(n+1)!}{k!(n+1-k)!}=\frac{n!}{(k-1)!(n+1-k)!}+\frac{n!}{k!(n-k)!}$$

which is straightforward.

cheers

the right hand side: $$\frac{n!}{(k-1)!(n+1-k)!}+\frac{n!}{k!(n-k)!} = \frac{n!.k+n!.(n+1-k)}{k!(n+1-k)!}=\frac{n!(k+n+1-k)}{k!(n+1-k)!}=\frac{n!(n+1)}{k!(n+1-k)!}=\frac{(n+1)!}{k!(n+1-k)!}$$ = the left hand side.