10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Have you tried to prove it via induction (over $n$)? $\endgroup$ – user127.0.0.1 Jan 29 '14 at 16:23
  • $\begingroup$ Your equation for the case $p=1$ is wrong. $\endgroup$ – user940 Jan 29 '14 at 16:37
  • $\begingroup$ Oh,Thank you,I have edit $\endgroup$ – china math Jan 29 '14 at 16:50
  • $\begingroup$ Just an idle thought, but the Snake Oil method (p. 118 of Wilf) might work. $\endgroup$ – André 3000 Jan 29 '14 at 17:24
  • 1
    $\begingroup$ A more or less random observation: multiplying by $\binom{pn}{n}$, the term on the LHS becomes $\binom{pn+k}{k,k,k,(p-1)n-k,n-k}$. $\endgroup$ – JiK Feb 2 '14 at 16:28
4
+50
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ $$ \sum(-1)^k\binom nk\binom mk\binom{-(n+m+1)}k $$ surely reminds of Dixon's identity... $\endgroup$ – Grigory M Feb 2 '14 at 20:52
  • $\begingroup$ Your second equation indeed follows from math.stackexchange.com/questions/280481 (applied to $n$, $x$ and $x+n+\alpha$ instead of $p$, $q$ and $n$). $\endgroup$ – darij grinberg Sep 4 '15 at 14:22
  • $\begingroup$ The first equation can be simplified by multiplying both sides with $\dbinom{x+y+n}{n}$ and then rewriting $\dbinom{n}{k}\dbinom{x+y+n}{n}/\dbinom{x+y+n}{k}$ as $\dbinom{x+y+n-k}{x+y}$ on the left hand side. Thus it becomes $\sum\limits_{k=0}^n \dbinom{x}{k} \dbinom{y}{k} \dbinom{x+y+n-k}{x+y} = \dbinom{x+n}{n} \dbinom{y+n}{n}$. This might follow from the second equation by upper negation or a similar trick, though I'm not sure; at any rate it is probably well-known. $\endgroup$ – darij grinberg Sep 4 '15 at 14:25
  • 1
    $\begingroup$ Yes, it does follow from the second equation by upper negation (for details, see Proposition 3.9(g) in cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf , or search for "assortment of other identities" if the numbering has changed.) $\endgroup$ – darij grinberg Sep 4 '15 at 14:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (I wonder if there is a binomial identity, generalizing both this one and Dixon's...) $\endgroup$ – Grigory M Feb 2 '14 at 21:55
1
$\begingroup$

Suppose we seek to verify that $$\sum_{k=0}^n {n\choose k} {pn-n\choose k} {pn+k\choose k} = {pn\choose n}^2.$$

We use the integrals $${pn-n\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{pn-n}}{z^{k+1}} \; dz$$

and $${pn+k\choose k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pn+k}}{w^{k+1}} \; dw.$$

This yields for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{pn-n}}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pn}}{w} \sum_{k=0}^n {n\choose k} \frac{(1+w)^k}{z^k w^k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{pn-n}}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pn}}{w} \left(1+\frac{1+w}{zw}\right)^n \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{pn-n}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{pn}}{w^{n+1}} (1+w+zw)^n \; dw \; dz.$$

Expanding the binomial in the inner sum we get $$\sum_{q=0}^n {n\choose q} w^q (1+z)^q$$ which yields $$\sum_{q=0}^n {n\choose q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{pn-n+q}}{z^{n+1}} {pn\choose n-q} \; dz \\ = \sum_{q=0}^n {n\choose q} {pn-n+q\choose n} {pn\choose n-q}.$$

The inner term is $${n\choose q} {pn-n+q\choose n} {pn\choose pn-n+q} \\ = \frac{(pn)!}{q!\times (n-q)! \times (pn-2n+q)! \times (n-q)!} \\ = {pn\choose n} \frac{n! \times (pn-n)!}{q!\times (n-q)! \times (pn-2n+q)! \times (n-q)!} \\ = {pn\choose n} {n\choose q} {pn-n\choose n-q}.$$

Thus it remains to show that $$\sum_{q=0}^n {n\choose q} {pn-n\choose n-q} = {pn\choose n}.$$

This can be done combinatorially or using the integral $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{pn-n}}{v^{n+1}} \sum_{q=0}^n {n\choose q} v^q \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{pn-n}}{v^{n+1}} (v+1)^n \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{pn}}{v^{n+1}} = {pn\choose n}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.