# Question about ${n+1\choose k} = {n\choose k} + {n\choose k-1}$ proof?

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.

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!$$
$(k-1)!k = k((k-1)\cdots 2\cdot 1) = k(k-1)\cdots 2\cdot 1 = k!$
$(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)!$
$(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.
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)!$