How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$

when $p=2$, then $$\sum_{k=0}^{n}\binom{n}{k}^2\binom{2n+k}{k}=\binom{2n}{n}^2$$

But I can't prove this

and I can't prove this $p\ge 3$ ?

Thank you for your help

Solution 1:

On p. 33 of this document the following appears:

"The following identity solves a problem on Page 122, Vol. 29, 1947 of Norsk Matematisk Tidsskrift." $$\sum_{k=0}^n \binom{n}{k}\frac{\binom{x}{k}\binom{y}{k}}{\binom{x+y+n}{k}} = \frac{\binom{x+n}{n}\binom{y+n}{n}}{\binom{x+y+n}{n}}$$ followed by $$\sum_{k=0}^n \binom{n}{k}\binom{x}{k}\binom{x+n+k+\alpha}{k+\alpha} = \binom{x+\alpha+n}{n}\binom{x+\alpha+n}{n+\alpha}.$$ Presumably the second equation can be derived from the first; in any case, setting $\alpha=0$ and $x=(p-1)n$ gives the identity you asked about.

To derive the latter identity, start with the left-hand side: \begin{align} \binom{n}{k}\binom{x}{k}&\binom{x+n+k+\alpha}{k+\alpha} = \frac{n!x!(x+n+\alpha+k)!}{k!(n-k)!k!(x-k)!(\alpha+k)!(x+n)!} \\ &= \frac{n!x!}{(n+x)!}\cdot\frac{(x+n+\alpha)!(x+n+\alpha+1)_k(-1)^k(-n)_k(-1)^k(-x)_k} {n!x!\alpha!(\alpha+1)_k(1)_k k!} \\ &= \frac{(x+n+\alpha)!}{\alpha!(x+n)!}\cdot\frac{(x+n+\alpha+1)_k(-n)_k(-x)_k} {(\alpha+1)_k(1)_kk!} \\ &= \frac{(x+n+\alpha)!}{\alpha!(x+n)!}{{_3F_2}\left(\left. \begin{array}{ccc} -n, & -x, & x+n+\alpha+1 \ \\ & 1, & \alpha+1 \end{array} \right\rvert\ {1}\right)}.\end{align} Saalsch\"utz' formula applies, giving \begin{align}\frac{(x+n+\alpha)!}{\alpha!(x+n)!}\cdot&\frac{(x+1)_n(-x-n-\alpha)_n}{(1)_n(-n-\alpha)_n} = \frac{(x+n+\alpha)!}{\alpha!(x+n)!}\cdot\frac{(x+n)!(x+n+\alpha)!\alpha!} {x!n!(x+\alpha)!(n+\alpha)!}\\ &= \frac{(x+n+\alpha)!}{n!(x+\alpha)!}\cdot\frac{(x+n+\alpha)!}{(n+\alpha)!x!} \\ &= \binom{x+n+\alpha}{n}\binom{x+n+\alpha}{n+\alpha}.\end{align}

Solution 2:

Let's (as @rogerl suggests) prove that $$ \sum\binom nk\binom mk\binom{n+m+k}{n+m}=\binom{n+m}n^2. $$

LHS can also be written as $$ \sum(-1)^k\binom nk\binom mk\binom{-(n+m+1)}k $$ so it's equal (oh, up to a sign) to the constant term of $$ (1-Z^{-1})^n(1-W^{-1})^m(1-ZW)^{-(n+m+1)} $$ i.e. to the residue $$ \operatorname*{res}_{Z,W}\left\{(1-Z^{-1})^n(1-W^{-1})^m(1-ZW)^{-(n+m+1)}\frac{dZ}Z\frac{dW}W\right\} $$ Now, like in a proof of Dixon's identity let's rewrite this in the form $$ \operatorname*{res}_{Z,W}\left\{ \left(\frac{1-Z^{-1}}{1-ZW}\right)^n \left(\frac{1-Z^{-1}}{1-ZW}\right)^m \frac{dZ\,dW}{ZW(1-ZW)}\right\} $$ and use the substitution $Z=\frac z{1-w}$, $W=\frac w{1-z}$. Since $\frac{dZ\,dW}{ZW(1-ZW)}=\frac{dz\,dw}{zw}$ and $\frac{1-Z^{-1}}{1-ZW}=-\frac z{(1-z)(1-w)}$ we see that our residue takes the form $$ \pm\operatorname*{res}_{z,w}\left\{\frac{(1-z)^{n+m}(1-w)^{n+m}}{z^nw^m}\frac{dz}z\frac{dw}w\right\}=\pm\binom{n+m}n\binom{n+m}m. $$ Bingo.