# An interesting identity: in search of a proof -Part I

I like the following binomial identity in that the RHS extracts the indeterminate $w$ from the LHS.

Question. Can you show that $$\sum_{k=0}^n\binom{x+kw}k\binom{y-kw}{n-k}=\sum_{k=0}^n\binom{x+y-k}{n-k}w^k\,\,\,?$$

It would be great if we can see alternative proofs? I've a bias for combinatorial arguments. :-)

• If we substitute $y:=v+nw$ in the identity, the LHS becomes a convolution of two similar sequences, which suggests to introduce the gf $f(x,w,z):=\sum_{k=0}^\infty \binom{x+kw}{k}z^k$, and try to identify the RHS as coefficient of $z^n$ in the expansion of $f(x,w,z)f(v,w,z)$. It appears $f$ has the form $f(x,w,z)=a(w,z)b(w,z)^x$, at least for $w=-1,0,1,2$, so the RHS would be $a(w,z)^2b(w,z)^{x+y}=a(w,z)f(x+y,w,z)$. – Pietro Majer May 18 '17 at 18:38
• That is an interesting approach. Perhaps we can expand on it. – T. Amdeberhan May 18 '17 at 18:41
• $f(x,w,z)$ is the generating function for the Hagen/Rothe coefficients of the second kind. Indeed, it has the form indicated by @Majer, where $b=b(w,z)$ is a solution of the implicit equation $z=\frac {b-1}{b^w}$, and $a(w,z)=\frac{b(w,z)}{(1-w) b(w,z) + w}$. – Luca Ghidelli May 18 '17 at 22:34

This is known as Jensen's identity and dates back to 1902. See here an overview of this identity and related ones, and a proof: https://arxiv.org/abs/1005.2745, a paper by Victor Guo.

• Cool, thanks. Now, let's wait for Part II. :-) – T. Amdeberhan May 18 '17 at 18:14

Oh no, I was too slow... sorry for the double reference. This is Jensen's identity. It first appeared (in a slightly modified form) in: Jensen, Sur une identité d'Abel et sur d'autres formules analogues, Acta Mathematica, vol 26 (1902) pp.307-318.

There is the following paper that gives elementary proofs to Jensen's identity and some generalizations or related formulas: Guo, On Jensen's and related combinatorial identities. Applicable Analysis and Discrete Mathematics Vol. 5, No. 2 (2011), pp. 201-211.

The elementary proof is very short, and consists just in a clever use of the Chu-Vandermonde convolution formula $$\sum_{k=0}^n \binom A k \binom B {n-k}=\binom {A+B} n\quad (1)$$ on the term $\binom {y-k\omega} k$ with $A=x+y+1$ and $A+B=y-k\omega$, followed by a straightforward change in the order of summation.  Then you get an equivalent identity  (just change of the names of the variables).

The proof of Chu's and Mohanty-Handa's multinomial generalization of Jensen's identity is similar, and involves a multinomial Chu-Vandermonde used iteratively.

Since (1) has combinatorial significance, it makes sense to rewrite Guo's computations avoiding changes of variables and negative binomials. You get an equivalent way of presenting the proof, which is slightly more amenable to combinatorial proofs. A key summation here is: $$\sum_{0\leq k\leq i\leq n} \binom {x+k\omega} k (-1)^{i-k} \binom {x+k\omega-k} {i-k} \binom {x+y-i} {n-i}.$$

Now it is possible to show that if you sum over $i$ first, you get the LHS of Jensen's identity, while you get the RHS summing over $k$. Moreover, both directions can possibly be proved combinatorially (assuming at least that $x$,$y$, and $\omega$ are integers).