Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$ Prove using factorials that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$
I think I'm having a bit of algebra problem with this proof. Here is my work thus far:$$\frac{n!}{k!(n-k)!}+2\frac{n!}{(k+1)!(n-k-1)!}+\frac{n!}{(k+2)!(n-k-2)!}\stackrel{?}{=}\frac{(n+2)!}{(k+2)!(n-k)!}$$$$\frac{(k+1)(k+2)n!}{(k+2)!(n-k)!}+\frac{2(k+2)(n-k)n!}{(k+2)!(n-k)!}+\frac{(n-k-1)(n-k)n!}{(k+2)!(n-k)!}\stackrel{?}{=}\frac{(n+2)!}{(k+2)!(n-k)!}$$$$\frac{n!({k^2}+{3k+2}+{2kn}-2k^2+4n-4k+n^2-kn-n+k^2+k)}{(k+2)!(n-k)!}\stackrel{?}{=}\frac{(n+2)!}{(k+2)!(n-k)!}$$$$\frac{n!(n^2+3n+2)}{(k+2)!(n-k)!}\stackrel{?}{=}\frac{(n+2)!}{(k+2)!(n-k)!}$$But from here I am stuck. How would I algebraically make these two sides match?
 A: Write down the LHS as
$${n \choose k} + {n \choose k+1} + {n \choose k+1} + {n \choose k+2}.$$
Now expand the first two terms to get ${n+1\choose k+1}$. The summation of the second two terms evaluates to ${n+1\choose k+2}$. The addition of the resulted two terms is the RHS.
A: To promote my comment to an answer: You've gotten to the point of comparing two quantities with equal denominator, so it suffices to show that
$$(n^2 + 3n + 2)n! = (n + 2)!$$
But this is equivalent to seeing that
$$n^2 + 3n + 2 = (n + 2)(n + 1)$$
which is clearly true.
A: Hint split the middle term as ${n\choose k+1}+{n\choose k+1}$ and then use ${n \choose r}+{n\choose r+1}={n+1\choose r+1}$ by proving it.
A: This result, and its generalizations, are made intuitively obvious by the relationship between Pascal's triangle and binomial coefficients; e.g., $$\begin{array}{ccccccc} \ldots & \binom{n}{k} & & \binom{n}{k+1} & & \binom{n}{k+2} & \ldots \\ & \ldots & \binom{n+1}{k+1} & & \binom{n+1}{k+2} & \ldots & \\ & & \ldots & \binom{n+2}{k+2} & \ldots & & \end{array}$$ and recalling that each coefficient is the sum of the two coefficients diagonally above it.
