Gosper's Identity $\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $ The page on Binomial Sums in Wolfram Mathworld http://mathworld.wolfram.com/BinomialSums.html (Equation 69) gives this neat-looking identity due to Gosper (1972):
$$\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $$
Would anyone know if there is a simple proof of this identity without using induction? 
 A: Hint: Suppose $0 \leq x \leq 1$, and consider a coin with bias $x$ being flipped until one of its sides comes up $n+1$ times. The left-hand side counts the probability that this happens, which is plainly $1$. Since both sides are polynomials in $x$ and the identity is true for infinitely many values of $x$, it must be true for all $x$.
A: Consider the expression
\begin{align}
\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]
\end{align}
in the following way. First consider the generating function of the series
\begin{align}
S_{n} = \sum_{k=0}^{n} \binom{k+n}{k} \, x^{k}
\end{align}
for which it is seen that
\begin{align}
\phi(x, t) &= \sum_{n=0}^{\infty} S_{n} \, t^{n} \\
&= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n+k}{k} x^{k} t^{n} \\
&= \sum_{n,k=0}^{\infty} \binom{2k+n}{k} (xt)^{k} t^{n} \\
&= (1-4xt)^{-1/2} \sum_{n=0}^{\infty} \left( \frac{2t}{1+\sqrt{1-4xt}} \right)^{n} \\
&= \frac{1}{\sqrt{1-4xt}} \cdot \frac{1+\sqrt{1-4xt}}{1-2t + \sqrt{1-4xt}},
\end{align}
where the series 
\begin{align}
\sum_{k=0}^{\infty} \binom{2k+n}{k} x^{k} = \frac{2^{n}}{\sqrt{1-4x} \, (1+\sqrt{1-4x})^{n}}
\end{align}
was used. This is equation (66) of the site referenced in the proposed problem.
Now, for $A = 1-4x(1-x)t$,
\begin{align}
\theta(x,t) &= x \phi(1-x, xt) + (1-x) \phi(x, (1-x)t) \\
&= \frac{1+\sqrt{A}}{\sqrt{A}} \left[ \frac{x}{1-2xt+ \sqrt{A}} + \frac{1-x}{1-2(1-x)t + \sqrt{A}} \right].
\end{align}
Making use of the definition of $A$ then 
\begin{align}
1-2xt+\sqrt{A} = \frac{1+\sqrt{A}}{2(1-x)} \, (1-2x + \sqrt{A})
\end{align}
and leads to
\begin{align}
\theta(x,t) &= \frac{1+\sqrt{A}}{\sqrt{A}} \left[ \frac{2x(1-x)}{(1+\sqrt{A})(1-2x+\sqrt{A}) } + \frac{2x(1-x)}{(1+\sqrt{A})(1-2(1-x)+\sqrt{A})} \right] \\
&= \frac{2x(1-x)}{\sqrt{A}} \left[ \frac{1}{1-2x+\sqrt{A}} + \frac{1}{1-2(1-x)+\sqrt{A}} \right] \\
&= \frac{4x(1-x)}{-1+4x(1-x) + A} \\
&= \left(\frac{1-A}{t}\right) \, \frac{1}{\left(\frac{1-A}{t}\right) - (1-A)} \\
&= \frac{1}{1-t} = \sum_{n=0}^{\infty} t^{n}.  
\end{align}
Since
\begin{align}
\theta(x,t) &= x \phi(1-x, xt) + (1-x) \phi(x, (1-x)t) \\
&= \sum_{n=0}^{\infty} \left[ \sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k] \, \right] \, t^{n}\\
&= \sum_{n=0}^{\infty} t^{n}
\end{align}
then by comparison of the coefficients of $\theta(x,t)$ the result follows as
\begin{align}
\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k] = 1.
\end{align}
A: Let $m>0$ a natural number and let's consider a set of polynomial functions:
$$A_{0}\left(x\right)=1$$
$$A_{n}\left(x\right)=\sum_{k=0}^{n}\binom{n+m}{k}x^{k}\left(1-x\right)^{n-k},\,\,\,\,n=1,\,2,\,3,\,\ldots$$
We have
$$A_{l}\left(x\right)=\sum_{k=0}^{l}\binom{l-1+m}{k}x^{k}\left(1-x\right)^{l-k}+\sum_{k=1}^{l}\binom{l-1+m}{k-1}x^{k}\left(1-x\right)^{l-k}$$
$$A_{l}\left(x\right)=\left(1-x\right)A_{l-1}\left(x\right)+\binom{l-1+m}{l}x^{l}+xA_{l-1}\left(x\right)$$
$$A_{l}\left(x\right)=A_{l-1}\left(x\right)+\binom{l-1+m}{l}x^{l},\,\,\,l=1,\,2,\,\ldots,\,n$$
Then
$$\sum_{l=1}^{n}A_{l}\left(x\right)=\sum_{l=0}^{n-1}A_{l}\left(x\right)+\sum_{l=1}^{n}\binom{l-1+m}{l}x^{l}$$
which leads to
$$A_{n}\left(x\right)=\sum_{k=0}^{n}\binom{m+k-1}{k}x^{k}.$$
i.e.
$$\sum_{k=0}^{n}\binom{n+m}{k}x^{k}\left(1-x\right)^{n-k}=\sum_{k=0}^{n}\binom{m+k-1}{k}x^{k}\, \, \left(1\right)$$
If we set $m=n+1$, we get:
$$\sum_{k=0}^{n}\binom{2n+1}{k}x^{k}\left(1-x\right)^{n-k}=\sum_{k=0}^{n}\binom{n+k}{k}x^{k}$$
for any natural number $n>0$.
Now
$$1=\left[x+\left(1-x\right)\right]^{2n+1}=\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^{k}\left(1-x\right)^{2n+1-k}$$
$$\sum_{k=0}^{n}\binom{2n+1}{k}x^{k}\left(1-x\right)^{2n+1-k}+\sum_{k=n+1}^{2n+1}\binom{2n+1}{k}x^{k}\left(1-x\right)^{2n+1-k}=1$$
$$\sum_{k=0}^{n}\binom{2n+1}{k}x^{k}\left(1-x\right)^{2n+1-k}+\sum_{k=n+1}^{2n+1}\binom{2n+1}{2n+1-k}x^{k}\left(1-x\right)^{2n+1-k}=1$$
$$\sum_{k=0}^{n}\binom{2n+1}{k}x^{k}\left(1-x\right)^{2n+1-k}+\sum_{k=0}^{n}\binom{2n+1}{k}x^{2n+1-k}\left(1-x\right)^{k}=1$$
$$\left(1-x\right)^{n+1}\sum_{k=0}^{n}\binom{2n+1}{k}x^{k}\left(1-x\right)^{n-k}+x^{n+1}\sum_{k=0}^{n}\binom{2n+1}{k}\left(1-x\right)^{k}x^{n-k}=1$$
Using $\left(1\right)$ we obtain:
$$\left(1-x\right)^{n+1}\sum_{k=0}^{n}\binom{n+k}{k}x^{k}+x^{n+1}\sum_{k=0}^{n}\binom{n+k}{k}\left(1-x\right)^{k}=1$$
or
$$\sum_{k=0}^{n}\binom{n+k}{k}\left[x^{n+1}\left(1-x\right)^{k}+\left(1-x\right)^{n+1}x^{k}\right]=1$$
which concludes the proof.
