1. Binomial proof

I have to prove that
n+1 choose k = n choose k + n choose k-1

Where on earth do I start? Any help much appreciated!

2. Originally Posted by eliz1906
I have to prove that
n+1 choose k = n choose k + n choose k-1

Where on earth do I start? Any help much appreciated!
Hi Eliz1906,

If we work from the right...

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

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

We express the sum with the same denominators as $\binom{n+1}{k}$

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

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

Therefore

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

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

$=\binom{n+1}{k}$

3. Hello, eliz1906!

It takes only algebra . . . a lot of it!

Prove: . ${n+1\choose k} \;=\;{n \choose k} + {n\choose k-1 }$

The right side is: . $\frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}$

Get a common denominator:

$\frac{n!}{k!(n-k)!}\cdot{\color{blue}\frac{(k-1)!(n-k+1)!}{(k-1)!(n-k+1)!}} \;+\; \frac{n!}{(k-1)!(n-k+1)!}\cdot{\color{blue}\frac{k!(n-k)!}{k!(n-k)!}}$

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

Factor: . $\frac{n!(k-1)!(n-k)!\,\bigg[(n-k+1) + k\bigg]}{k! (k-1)! (n-k)!(n-k+1)!}$

Reduce: . $\frac{n!{\color{red}\rlap{///////}}(k-1)!{\color{green}\rlap{///////}}(n-k)!\,\bigg[(n-k+1) + k\bigg]}{k! {\color{red}\rlap{///////}}(k-1)! {\color{green}\rlap{///////}}(n-k)!(n-k+1)!}$

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

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

. . . . . . $=\quad {n+1\choose k}$

Edit: Ah, Archie beat me to it!
. . . .But I'm not deleting all this work . . . So there!
.

4. Thank you SOOO much.

5. Sorry Soroban!

I was quick out of the blocks there!
I'm always glad to see you join in.

Your post was beautifully illustrated, I must say.