Question

I need to prove that (n Choose k) + (n Choose (k-1)) = ((n+1) Choose k). How do I do this?

Answer 1

work on it... both sides of the equation \[_n C_k+_n C_\left(k-1\right)=_\left(n+1\right) C_k\]

Answer 2

applying \[_nC_r=\frac{n!}{r!(n-r)!}\]

Answer 3

I've tried that. I got n!/((n-k)!k!) + n!/((n-k+1)!(k-1)!) = (n+1)!

Answer 4

ive seen this recently while revising burton's number theory book and liked the proof -

consider this identity :-
\(\large \frac{1}{k} + \frac{1}{n-k+1} = \frac{n+1}{k(n-k+1)}\)

multiply \(\large \color{red}{\frac{n!}{(k-1)!(n-k)!}}\) both sides

\(\large \frac{\color{red}{n!}}{\color{red}{(k-1)!(n-k)!}k} + \frac{\color{red}{n!}}{\color{red}{(k-1)!(n-k)!}(n-k+1)} = \frac{\color{red}{n!}(n+1)}{\color{red}{(k-1)!(n-k)!}k(n-k+1)}\)


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


\(\large ^nC_k + ^nC_{k-1} = ^{n+1}C_k\)