3
$\begingroup$

I've found past proofs of this problem and for the most part I'm able to follow.

$$\eqalign{{n\choose k}+{n\choose k-1}&= {n!\over (n-k)!k!}+ {n!\over (n-(k-1))! (k-1)!} \text{ (step 1)}\cr &={n!\over (n-k)!k!}+ {n!\over (n-k+1)! (k-1)!}\text{ (step 2)}\cr &={(n-k+1)n!\over(n-k+1) (n-k)!k!}+ {n!k\over (n-k+1)! (k-1)! k}\text{ (step 3)}\cr &={(n-k+1)n! + n!k\over (n-k+1)! k!}\text{ (step 4)}\cr &={n\cdot n !-kn!+n!+n!k\over (n-k+1)! k!}\cr &={n\cdot n ! +n! \over (n-k+1)! k!}\cr &={n!(n+1) \over (n-k+1)! k!}\cr &={(n+1)! \over( (n+1)-k)! k!}\cr &={n+1\choose k}. }$$ My question is this: what happens to (n-k)! and (k-1)! in the denominators of step 3? Somehow the two denominators are reduced to (n-k+1)!k! in step 4 and for the life of me I can't understand where (n-k)! and (k-1)! went. I'm sure it's simple and I'm going to feel stupid when it's explained but for now I've been staring that this for about an hour and just can't get wrap my mind around it. Thanks for any help.

$\endgroup$
3
$\begingroup$

Recall that $m! = m(m-1)! = m(m-1)(m-2)!$ and so on. Likewise, we know that: $$ (a + 1)! = (a + 1)a!$$ So what we did here was absorb an extra term into each factorial: $$ (n−k+1)(n−k)! = (n - k + 1)! $$ where in this case we took $a = n - k$. Likewise: $$ k(k - 1)! = k! $$

$\endgroup$
1
$\begingroup$

$(k-1)!k = k((k-1)\cdots 2\cdot 1) = k(k-1)\cdots 2\cdot 1 = k!$

Similarly,

$(n-k+1)(n-k)! = (n-k+1)((n-k)\cdots 2\cdot 1) =(n-k+1)(n-k)\cdots 2\cdot 1 = (n-k+1)!$

$\endgroup$
1
$\begingroup$

$(n-k)!$ is just the product of all numbers from $(n-k)$ down to 1. So if we multiply this by $(n-k+1)$, the number one bigger, we just get $(n-k+1)!$. E.g. also $(n+1)\cdot n! = (n+1)!$ etc.

$\endgroup$
0
$\begingroup$

Take the LCM of the denominators and clearly $(n-k+1)!k!$ is divisible by both $(n-k)!k!$ and $(n-k+1)!(k-1)!$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.