# 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?

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$.

• Thank you! This is a very nice and clear interpretation. Was actually looking for a mathematical derivation from LHS to RHS. Would like to accept both this answer and the other one but MSE doesn't allow this currently, so to be fair will leave it. Have upvoted the answer :) – hypergeometric Sep 22 '14 at 3:37

Suppose we seek to show that $$\sum_{k=0}^n {n+k\choose k}(x^{n+1}(1-x)^k+(1-x)^{n+1}x^k) =1.$$

We use an Iverson bracket to control the range of $k$ so we can let it range from zero to infinity, which is

$$[[0 \le k\le n]] = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1+v+\cdots+v^n}{v^{k+1}} \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{v^{n+1}-1}{(v-1)v^{k+1}} \; dv.$$

We evaluate this using the formula for the residue at infinity $$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

which in this case yields (omit the minus sign as the residues sum to zero) $$\mathrm{Res}_{v=0} \frac{1}{v^2} \frac{1/v^{n+1}-1}{(1/v-1) \times 1/v^{k+1}} = \mathrm{Res}_{v=0} \frac{1/v^{n+1}-1}{(1-v) \times 1/v^{k}} \\ = \mathrm{Res}_{v=0} \left(\frac{v^{k}}{v^{n+1}}\frac{1}{1-v} -\frac{v^k}{1-v}\right).$$

With the additional assumption that $k \ge 0$ which is the case here this yields $$\mathrm{Res}_{v=0} \frac{v^{k}}{v^{n+1}}\frac{1}{1-v} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{v^{k}}{v^{n+1}}\frac{1}{1-v} \; dv$$ which could have been obtained by inspection.

This yields for the second component of the sum $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n+1}}\frac{1}{1-v} \sum_{k\ge 0} {n+k\choose n} (1-x)^{n+1} x^{k} v^k \; dv \\ = (1-x)^{n+1} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n+1}}\frac{1}{1-v} \frac{1}{(1-xv)^{n+1}} \; dv.$$

We will evaluate this not by evaluating the residue at zero but the sum of the negatives of the residues at $v=1$ and $v=1/x$ given that the residues sum to zero.

For the residue at $v=1$ re-write the integral as follows: $$-(1-x)^{n+1} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n+1}}\frac{1}{v-1} \frac{1}{(1-xv)^{n+1}} \; dv.$$

The residue at $v=1$ here is $$-(1-x)^{n+1} \frac{1}{(1-x)^{n+1}} = -1$$ for a contribution of $$1$$ upon negation.

For the residue at $v=1/x$ re-write the integral as follows: $$\frac{(1-x)^{n+1}}{x^{n+1}} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n+1}}\frac{1}{1-v} \frac{1}{(1/x-v)^{n+1}} \; dv \\ = (-1)^{n+1} \frac{(1-x)^{n+1}}{x^{n+1}} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{n+1}}\frac{1}{1-v} \frac{1}{(v-1/x)^{n+1}} \; dv.$$

Use Leibniz' rule to differentiate the two terms in $v$ to get

$$\frac{1}{n!}\left( \frac{1}{v^{n+1}}\frac{1}{1-v} \right)^{(n)} = \frac{1}{n!} \sum_{k=0}^n {n\choose k} \frac{(-1)^k (n+k)!}{n! \times v^{n+1+k}} \frac{(n-k)!}{(1-v)^{n-k+1}}.$$

Evaluate this at $v=1/x$ including the factor in front to get for the residue $$(-1)^{n+1} \frac{(1-x)^{n+1}}{x^{n+1}} \frac{1}{n!} \sum_{k=0}^n {n\choose k} \frac{(-1)^k (n+k)!}{n! \times (1/x)^{n+1+k}} \frac{(n-k)!}{(1-1/x)^{n-k+1}} \\ = (-1)^{n+1} \frac{(1-x)^{n+1}}{x^{n+1}} \sum_{k=0}^n \frac{(-1)^k (n+k)!}{n! \times k! \times (1/x)^{n+1+k}} \frac{1}{(1-1/x)^{n-k+1}} \\ = (-1)^{n+1} (1-x)^{n+1} \sum_{k=0}^n {n+k\choose k} \frac{(-1)^k}{(1/x)^{k}} \frac{1}{(x-1)^{n-k+1}/x^{n-k+1}} \\ = \sum_{k=0}^n {n+k\choose k} \frac{(-1)^k}{(1/x)^{k}} \frac{1}{(x-1)^{-k}/x^{n-k+1}} \\ = x^{n+1} \sum_{k=0}^n {n+k\choose k} (1-x)^k.$$

Upon negation this becomes the negative of the first component of the sum. Hence adding the three pieces (first component, one, negative of first component) we obtain a sum of

$$1.$$

Remark. If we want to do this properly we also need to verify that the residue at infinity of the integral in $v$ is zero.

In the present case this becomes

$$- \mathrm{Res}_{v=0} \frac{1}{v^2} \frac{1}{(1/v)^{n+1}}\frac{1}{1-1/v} \frac{1}{(1-x/v)^{n+1}} \\ = - \mathrm{Res}_{v=0} \frac{1}{v^2} \frac{v^{n+1} \times v^{n+1}}{1-1/v} \frac{1}{(v-x)^{n+1}} \\ = - \mathrm{Res}_{v=0} \frac{1}{v} \frac{v^{2n+2}}{v-1} \frac{1}{(v-x)^{n+1}} \\ = - \mathrm{Res}_{v=0} \frac{v^{2n+1}}{v-1} \frac{1}{(v-x)^{n+1}}$$ which is zero by inspection.

• Funny thing. You've already solved it in that generality. :-) – Markus Scheuer Jan 15 '18 at 21:36
• There is a user at this MSE link who is asking about the substitution rule for formal power series which you have used many times. – Marko Riedel Feb 4 '18 at 21:17
• Answer added. Thanks for the hint. – Markus Scheuer Feb 4 '18 at 22:06
• I think OP is asking specifically about the substitution rule $A(z) = \sum z^k [u^k] A(u)$ which is what ACE refers to (consult my posts). Hence a pointer to your work on this perhaps including an example would probably be helpful, keeping what you have already posted. – Marko Riedel Feb 4 '18 at 22:12
• Ah, I see. Thanks for the info. – Markus Scheuer Feb 4 '18 at 22:13

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}

• Thank you! This looks like a very detailed derivation. How did you get from the 2nd to the 3rd line after "for which it is seen that"? Would have liked to accept both this answer and the other one but as MSE currently doesn't allow it, will leave it for now. Have upvoted the answer :) – hypergeometric Sep 22 '14 at 3:40
• @hypergeometic It is one of the many index shifting theorems. It follows from \begin{align} \sum_{n=0}^{\infty} \sum_{k=0}^{n} B(k,n) = \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} B(k,n+k) \end{align} – Leucippus Sep 22 '14 at 19:04
• thank you for the explanation! – hypergeometric Sep 23 '14 at 15:53

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.