# Prove $(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}$

I stumbled upon the identity $$(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}.$$

The right-hand side is a polynomial. This is easy to verify for small $k$, but I don't see a simple proof for all $k$. Can anyone help?

Edit: It should perhaps be noted that the right-hand side is essentially a Narayana polynomial ${N_k}(x) = \sum\limits_{j = 1}^k \binom{k}{j-1}\binom{k}{j}/k x^j.$

More precisely ${\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}=(k+1) N_k(x).$

Edit after the answer by Kelenner:

After studying both ideas of Kelenner in more detail I have seen that both lead to a proof of the proposed identity if one is willing to accept computer proofs. As I have stated in a comment the first idea leads to the identity $$\sum\limits_{m = 0}^k \binom{k-1}{m}\binom{2k-m}{k}x^{k-m}(1-x)^m={\sum\limits_{j= 0}^k \binom{k-1}{j-1}\binom{k+1}{j} x^j}.$$ My first reaction was that this leads to ugly binomial sums and therefore at first I did not study it further. I prefer in general proofs by hand but then I was curious to see if it could be done by computer. And it worked. Comparing coefficients of $x^j$ this identity reduces to $$\sum\limits_{m = 0}^k (-1)^{j-m}\binom{k-1}{k-m}\binom{k+m}{k}\binom{k-m}{j-m}=\binom{k-1}{j-1}\binom{k+1}{j}.$$ After dividing by the RHS we get a sum which should be the constant $1$. To this sum I applied the Mathematica Fast Zeilberger Package by Peter Paule, Markus Schorn and Axel Riese and got the desired result. In the same way the partial fraction identity for the Narayana polynomials can be proved.

• In the RHS, is $j \geq 0$ or $1$ Jul 17, 2014 at 15:55
• This does not matter because $\binom{k-1}{-1}=0.$ Jul 17, 2014 at 16:27
• A related question. Oct 27, 2015 at 23:55
• This is consequence of Euler's transformation for Gauss hypergeometric function.
– Nemo
May 28, 2019 at 14:44

Suppose we start by evalutating the two sums in turn, where the parameter $k\ge 1$.

For the first we will be using the following integral representation: $${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz.$$

We seek $$\sum_{n\ge 1} {n-1+k\choose k} {n+k\choose k} x^n.$$

Using the integral we find $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{n\ge 1} {n-1+k\choose k} x^n \frac{(1+z)^{n+k}}{z^{k+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^k}{z^{k+1}} \sum_{n\ge 1} {n-1+k\choose k} (1+z)^n x^n \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{x(1+z)^{k+1}}{z^{k+1}} \sum_{n\ge 1} {n-1+k\choose k} (1+z)^{n-1} x^{n-1} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{x(1+z)^{k+1}}{z^{k+1}} \frac{1}{(1-x(1+z))^{k+1}} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{x(1+z)^{k+1}}{z^{k+1}} \frac{1}{(1-x-xz))^{k+1}} \; dz \\= \frac{1}{(1-x)^{k+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{x(1+z)^{k+1}}{z^{k+1}} \frac{1}{(1-xz/(1-x)))^{k+1}} \; dz \\ = \frac{x}{(1-x)^{k+1}} \sum_{q=0}^k {k+1\choose k-q} {q+k\choose k} \left( \frac{x}{1-x} \right)^q \\ = \frac{x}{(1-x)^{k+1}} \sum_{q=0}^k {k+1\choose q+1} {q+k\choose k} \left( \frac{x}{1-x} \right)^q.$$

Applying the integral representation from the beginning a second time we obtain for this sum $$\frac{x}{(1-x)^{k+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{q=0}^k {k+1\choose q+1} \frac{(1+z)^{q+k}}{z^{k+1}} \left( \frac{x}{1-x} \right)^q\; dz \\ = \frac{x}{(1-x)^{k+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^k}{z^{k+1}} \sum_{q=0}^k {k+1\choose q+1} (1+z)^q \left( \frac{x}{1-x} \right)^q\; dz \\ = \frac{1}{(1-x)^k} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} \sum_{q=0}^k {k+1\choose q+1} (1+z)^{q+1} \left( \frac{x}{1-x} \right)^{q+1}\; dz \\ = \frac{1}{(1-x)^k} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} \left(-1 + \left(1+(1+z)\frac{x}{1-x}\right)^{k+1}\right) \; dz.$$

We have $k+1-(k-1) = 2$, so the first component inside the parentheses drops out, leaving

$$\frac{1}{(1-x)^k} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} \left(1+(1+z)\frac{x}{1-x}\right)^{k+1} \; dz \\ = \frac{1}{(1-x)^{2k+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} \left(1-x+x(1+z)\right)^{k+1} \; dz \\ = \frac{1}{(1-x)^{2k+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} \left(1+xz\right)^{k+1} \; dz.$$

We need one more simplification on this and put $z=1/w$, getting $$\frac{1}{(1-x)^{2k+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+1/w)^{k-1}}{(1/w)^{k+1}} \left(1+x/w\right)^{k+1} \; \frac{1}{w^2} dw \\ = \frac{1}{(1-x)^{2k+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} w^2 (w+1)^{k-1} \left(\frac{w+x}{w} \right)^{k+1} \; \frac{1}{w^2} dw \\ = \frac{1}{(1-x)^{2k+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(w+1)^{k-1}}{w^{k+1}} (w+x)^{k+1}\; dw.$$

The reson this works is because we are essentially evaluating the residue at infinity and the residues sum to zero. This concludes the evaluation of the first sum.

For the second we will be using the following integral representation: $${k-1\choose j-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^j} \; dz.$$

We seek $$\sum_{j\ge 1} {k+1\choose j} {k-1\choose j-1} x^j.$$

Using the integral we find $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{j\ge 1} {k+1\choose j} x^j \frac{(1+z)^{k-1}}{z^j} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{k-1} \sum_{j\ge 1} {k+1\choose j} \frac{x^j}{z^j} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{k-1} \left(-1 + (1+x/z)^{k+1} \right) \; dz.$$

The entire component drops out, leaving $$\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{k-1} (1+x/z)^{k+1} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k-1}}{z^{k+1}} (z+x)^{k+1} \; dz.$$

This however is precisely the integral that we had for the first sum without the factor in front, done.

The only infinite sum appearing here is the first one with convergence when $|(1+z)x|<1.$ Therefore choosing $|x|\lt 1/Q$ and $|z|\lt 1/Q$ with $Q\ge 2$ we have $|(Q+1)/Q/Q|= |1/Q^2 + 1/Q|<1$ and get convergence of the first LHS integral in a neighborhood of zero.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

We have for $k\geq 1$: $$g_k(x)=\frac{x^k}{k!}(\frac{d}{dx})^k (\frac{1}{1-x})=\frac{x^k}{(1-x)^{k+1}}=\frac{x^k}{k!}(\frac{d}{dx})^k(\sum_{m\geq 0}x^m)=\sum_{m\geq k}\binom{m}{k}x^m$$

Now put $\displaystyle f_k(x)=\sum_{m\geq k}\binom{m}{k}x^{m-1}$.

We have:

$$f_k^{(k)}(x)=\sum_{m\geq k}\binom{m}{k}(m-1)\cdots ((m-1)-k+1)x^{m-1-k}$$ Hence:

$$\frac{f_k^{(k)}(x)}{k!}=\sum_{m\geq k}\binom{m}{k}\binom{m-1}{k} x^{m-k-1}$$

Putting $m=k+n$ gives: $$\frac{f_k^{(k)}(x)}{k!}=\sum_{n\geq 0}\binom{n+k}{k}\binom{n+k-1}{k}x^{n-1}$$

Hence

$$\sum_{n\geq 0}\binom{n+k}{k}\binom{n+k-1}{k}x^{n}=\frac{x}{k!}(\frac{d}{dx})^{k}(x^{k-1}(1-x)^{-k-1})$$

Now I think that you can finish by using Leibniz Formula.

As this does not work, here is a new idea. We have

$$\sum_{n\geq 0}\binom{n+k}{k}\binom{n+k-1}{k}x^{n}=\frac{x}{k!}(\frac{d}{dx})^{k}(x^{k-1}(1-x)^{-k-1})$$ I write $$x^{k-1}=(x-1+1)^{k-1}=\sum_{j=0}^{k-1}\binom{k-1}{j}(x-1)^j=\sum_{j=0}^{k-1}\binom{k-1}{j}(-1)^j(1-x)^j$$ and

$$P_k(x)=(1-x)^{2k+1}\sum_{n\geq 0}\binom{n+k}{k}\binom{n+k-1}{k}x^{n}=\frac{x}{k!}(1-x)^{2k+1}(\frac{d}{dx})^{k}(\sum_{j=0}^{k-1}\binom{k-1}{j}(-1)^j(1-x)^{j-k-1})$$

We have hence (if I have not made a mistake):

$$P_k(x)=x\sum_{j=0}^{k-1}\binom{k-1}{j}\binom{2k-j}{k}(x-1)^j$$

This is very close to the formula 1.3 given in http://arxiv.org/pdf/0805.1274v1.pdf, page 2. The factor $x$ must be written as $x-1+1$ of course to see if this is the same. And of course, the proof of the formula 1.3 can be complicated.

• This is a nice idea, but it seems that the difficulty has only been shifted from one binomial identity to another one. The numerator of the RHS gives $\sum\limits_{m = 0}^k \binom{k-1}{m}\binom{2k-m}{k}x^{k-m}(1-x)^m.$ Thus it remains to show that $\sum\limits_{m = 0}^k \binom{k-1}{m}\binom{2k-m}{k}x^{k-m}(1-x)^m={\sum\limits_{j= 0}^k \binom{k-1}{j-1}\binom{k+1}{j} x^j},$ which leads again to ugly binomial sums. Jul 18, 2014 at 10:34
• @Johann Cigler OK, sorry, I have not done the computations. To have a new idea seems difficult. Jul 18, 2014 at 11:38
• If I have understood it correctly the paper by Mansour and Sun has given the numerator of the partial fraction expansion of $\frac{N_n(x)}{{(1-x)^n}}$ and you have shown that $P_k(x)$ does the same for the LHS of my sought for identity. Thus I must study the above paper in order to understand the identity. Thank you for your help and the reference. Jul 18, 2014 at 14:25