# 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 $\displaystyle k \geq 1$
$\displaystyle n C k + n C (k-1) = \frac{n!}{(n-k)!k!} + \frac{n!}{(k-1)!(n-k+1)!}$

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

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

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

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

$\displaystyle \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 $\displaystyle \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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}