# combination

• Feb 1st 2013, 11:10 PM
miki
combination
why is "nCk + nCk-1" equal to " n+1Ck " ?

• Feb 2nd 2013, 12:03 AM
jakncoke
Re: combination
Algebriacally, well Assume $k \geq 1$
$n C k + n C (k-1) = \frac{n!}{(n-k)!k!} + \frac{n!}{(k-1)!(n-k+1)!}$

Observe that $(n-k+1)! = (n-k)!*(n-k+1)$ (1)

so $\frac{n!}{(n-k)!k!} + \frac{k * n! }{k*(k-1)!(n-k+1)!}$ (i can do this since k/k = 1)

$\frac{n!}{(n-k)!k!} + \frac{k * n! }{k!(n-k)!(n-k+1)}$ (im using (1) )

multiply the first equation by $\frac{(n-k+1)}{(n-k+1)}$ to get both denominaters equals

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

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

which is n+1 C k.