<s>[INST] 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.
 [/INST] 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}.$$
</s>