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

Question

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.

Answer 1

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.

Answer 2

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.