combinatorics - Combinatorial identity's algebraic proof without induction.

How would you prove this combinatorial idenetity algebraically without induction?

$$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$

Thanks.

Answer

Here is an algebraic approach. In order to do so it's convenient to use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g.
\begin{align*}
\binom{n}{k}=[z^k](1+z)^n
\end{align*}

We obtain

\begin{align*}
\sum_{k=0}^{n}\binom{x+k}{k}&=\sum_{k=0}^{n}\binom{-x-1}{k}(-1)^k\tag{1}\\
&=\sum_{k=0}^n[z^k](1+z)^{-x-1}(-1)^k \tag{2}\\
&=[z^0]\frac{1}{(1+z)^{x+1}}\sum_{k=0}^n\left(-\frac{1}{ z }\right)^k\tag{3}\\
&=[z^0]\frac{1}{(1+z)^{x+1}}\cdot \frac{1-\left(-\frac{1}{z}\right)^{n+1}}{1-\left(-\frac{1}{z}\right)}\tag{4}\\
&=[z^n]\frac{z^{n+1}+(-1)^n}{(1+z)^{x+2}}\tag{5}\\
&=(-1)^n[z^n]\sum_{k=0}^\infty\binom{-x-2}{k}z^k\tag{6}\\

&=(-1)^n\binom{-x-2}{n}\tag{7}\\
&=\binom{x+n+1}{n}\tag{8}
\end{align*}
and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.





• In (2) we apply the coefficient of operator.




• In (3) we do some rearrangements by using the linearity of the coefficient of operator and we also use the rule
  \begin{align*}
  [z^{p-q}]A(z)=[z^p]z^{q}A(z)
  \end{align*}




• In (4) apply the formula for the finite geometric series.




• In (5) we do some simplifications and use again the rule stated in comment (3).




• In (6) we use the geometric series expansion of $\frac{1}{(1+z)^{x+2}}$. Note that we can ignore the summand $z^{n+1}$ in the numerator since it has no contribution to the coefficient of $z^n$.




• In (7) we select the coefficient of $z^n$.




• In (8) we use the rule stated in comment (1) again.