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.
 A: 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.
A: Hint: The R.H.S counts how many ways you can arrange $x+1$ $A$s and $n$ $B$s in a $x+n+1$ long sequence. As for the L.H.S, consider how many of these such sequences end in exactly $j$ $B$s as $j$ varies from $0$ to $n$. Hope this helps! Feel free to ask for extra clarification.
A: Suppose we seek to verify that
$$\sum_{k=0}^n {q+k\choose k} = {q+n+1\choose n}.$$
The difficulty here lies in the fact that the binomial coefficients on
the LHS do not have an upper bound for the sum wired into them. We use
an Iverson bracket to get around this:
$$[[0\le k\le n]]
= \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{w^k}{w^{n+1}} \frac{1}{1-w} \; dw.$$
Introduce furthermore
$${q+k\choose k} = {q+k\choose q} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q+k} \; dz.$$
With  the  Iverson bracket  in  place  we can  let  the  sum range  to
infinity, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q} 
\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\sum_{k\ge 0} w^k (1+z)^k
\; dw\; dz.$$
This converges when $|w(1+z)| < 1.$ Simplifying we have
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q} 
\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{1-w(1+z)}
\; dw\; dz.$$
Now the residues of the inner  integral sum to zero so we can evaluate
it  by  computing  the  negative  of  the residues  at  $w=1$  and  at
$w=1/(1+z).$ We get for the first one
$$- \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+2}} 
(1+z)^{q} \; dz = - [z^{q+1}] (1+z)^q = 0.$$
For the second one we have
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q-1} 
\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{1/(1+z)-w}
\; dw\; dz.$$
This yields
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q-1} 
(1+z)^{n+1}
\frac{1}{1-1/(z+1)} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+2}} 
(1+z)^{q+n+1} \; dz
= {q+n+1\choose q+1}
= {q+n+1\choose n}.$$
This concludes the argument.
In order to  be rigorous we must show that  the residue at infinity
of the inner integral is zero. We get
$$\mathrm{Res}_{w=\infty}
\frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{1-w(1+z)}
\\ = - \mathrm{Res}_{w=0} \frac{1}{w^2}
w^{n+1} \frac{1}{1-1/w} \frac{1}{1-(1+z)/w}
\\ = - \mathrm{Res}_{w=0} 
w^{n+1} \frac{1}{w-1} \frac{1}{w-(1+z)}.$$
There  is most  certainly  no pole  here  an the  residue  is zero  as
claimed (note that $1+z$ circles the value one.)
Addendum. I  just realized  that it is  actually a  lot simpler
without the Iverson bracket. We get
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q} 
\sum_{k=0}^n (1+z)^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+1}} 
(1+z)^{q} 
\frac{(1+z)^{n+1}-1}{1+z-1}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{q+2}} 
(1+z)^{q} 
((1+z)^{n+1}-1)
\; dz.$$
This has two pieces, the second is
$$-[z^{q+1}] (1+z)^q = 0$$
and the first is
$$[z^{q+1}] (1+z)^{q+n+1} = {q+n+1\choose q+1}
= {q+n+1\choose n}.$$
