# Another combinatorial identity of McKay

Suppose $v\ge 2$ and $s\ge 1$ are integers. I'm stuck trying to show that

$$v\sum_{k=0}^{s-1} \binom{2s}{k} \frac{s-k}{s}(v-1)^k = \sum_{k=0}^s \binom{2s}{k} \frac{2s-2k+1}{2s-k+1}(v-1)^k$$

I've tried residues and Egorychev's method, generating functions, and just plain rearranging, but nothing has worked yet. I think my main difficulty is figuring out how to get the fraction factor on the right to come out of the leftmost expression. Any hints or solutions would be much appreciated.

EDIT: See this question for another form of the expression on the left hand side above.

EDIT: I've been able to show by appealing to some combinatorial identities due to Lerch that $$\binom{2s}{k}\frac{2s-2k+1}{2s-k+1} = \binom{2k}{k}\left( \sum_{n\ge 0} \frac{\binom{2k}{n+k}}{\binom{2s}{n+k}} \right)^{-1}$$ The expression being inverted on the right can be written as a hypergeometric function, but so far this hasn't helped me proceed.

• Have you tried $k\mapsto s-k$ on the right ? – Lucian Dec 1 '15 at 9:06
• @Lucian Yes. Perhaps I'm missing something? – sourisse Dec 1 '15 at 15:46

Suppose we seek to show that $$v \sum_{k=0}^{n-1} {2n\choose k} \frac{n-k}{n} (v-1)^k = \sum_{k=0}^{n} {2n\choose k} \frac{2n-2k+1}{2n-k+1} (v-1)^k.$$

Now the coefficient on $[v^q]$ on the left is $$\sum_{k=0}^{n-1} {2n\choose k} \frac{n-k}{n} {k\choose q-1} (-1)^{k-(q-1)}$$

and on the right it is $$\sum_{k=0}^{n} {2n\choose k} \frac{2n-2k+1}{2n-k+1} {k\choose q} (-1)^{k-q}.$$

Re-factor these to obtain $$\sum_{k=0}^{n-1} {2n\choose q-1} \frac{n-k}{n} {2n-(q-1)\choose k-(q-1)} (-1)^{k-(q-1)} \\ = {2n\choose q-1} \sum_{k=0}^{n-1} \frac{n-k}{n} {2n-(q-1)\choose k-(q-1)} (-1)^{k-(q-1)}$$

and $$\sum_{k=0}^{n} {2n\choose q} \frac{2n-2k+1}{2n-k+1} {2n-q\choose k-q} (-1)^{k-q} \\ = {2n\choose q} \sum_{k=0}^{n} \frac{2n-2k+1}{2n-k+1} {2n-q\choose k-q} (-1)^{k-q} .$$

Now the left side can be re-written as follows: $$\frac{q}{2n-q+1} {2n\choose q} \sum_{k=0}^{n-1} \frac{n-k}{n} {2n-(q-1)\choose k-(q-1)} (-1)^{k-(q-1)}.$$

We have reduced the problem to the following claim: $$\frac{q}{2n-q+1} \sum_{k=0}^{n-1} \frac{n-k}{n} {2n-q+1\choose k-q+1} (-1)^{k-(q-1)} \\ = \sum_{k=0}^{n} \frac{2n-2k+1}{2n-k+1} {2n-q\choose k-q} (-1)^{k-q}$$

which is $$\frac{1}{n} \frac{q}{2n-q+1} \sum_{k=0}^{n-1} (n-k) {2n-q+1\choose k-q+1} (-1)^{k-(q-1)} \\ = \frac{1}{2n-2q+1} \sum_{k=0}^{n} (2n-2k+1) {2n-q+1\choose k-q} (-1)^{k-q}$$

or $$\frac{q}{n} \sum_{k=0}^{n-1} (n-k) {2n-q+1\choose k-q+1} (-1)^{k-(q-1)} \\ = \sum_{k=0}^{n} (2n-2k+1) {2n-q+1\choose k-q} (-1)^{k-q}.$$

The left here is $$\frac{q}{n} \sum_{k=1}^{n} k {2n-q+1\choose n-k-q+1} (-1)^{n-k-(q-1)} \\ = (-1)^{n-q+1} \frac{q}{n} \sum_{k=0}^{n} k {2n-q+1\choose n-k-q+1} (-1)^{k} .$$

Introduce $${2n+1-q\choose n-q-k+1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q-k+2}} (1+z)^{2n+1-q} \; dz.$$

Observe that this controls the range being zero when $k\gt n-q$ so we may extend $k$ to infinity to obtain for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+2}} (1+z)^{2n+1-q} (-1)^{n-q+1} \frac{q}{n} \sum_{k\ge 0} (-1)^k k z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+2}} (1+z)^{2n+1-q} (-1)^{n-q} \frac{q}{n} \frac{z}{(1+z)^2} \; dz \\ = (-1)^{n-q} \frac{q}{n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n-1-q} \; dz \\ = (-1)^{n-q} \frac{q}{n} {2n-1-q\choose n-q} = (-1)^{n-q} \frac{q}{n} {2n-1-q\choose n-1}.$$

For the right we get two pieces call them $R_1$ and $R_2$ which are $$\sum_{k=0}^{n} {2n-q+1\choose k-q} (-1)^{k-q} \\ = (-1)^{n-q} \sum_{k=0}^{n} {2n-q+1\choose n-k-q} (-1)^{k}$$

and $$\sum_{k=0}^{n} (2n-2k) {2n-q+1\choose k-q} (-1)^{k-q} \\ = 2 (-1)^{n-q} \sum_{k=0}^{n} k {2n-q+1\choose n-k-q} (-1)^{k}.$$

Introduce once more $${2n+1-q\choose n-q-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q-k+1}} (1+z)^{2n+1-q} \; dz$$

to get for $R_1$ $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n+1-q} (-1)^{n-q} \sum_{k\ge 0} (-1)^{k} z^k \; dz \\ = (-1)^{n-q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n+1-q} \frac{1}{1+z} \; dz \\ = (-1)^{n-q} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n-q} \; dz \\ = (-1)^{n-q} {2n-q\choose n-q} = (-1)^{n-q} {2n-q\choose n}.$$

and for $R_2$

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n+1-q} 2 (-1)^{n-q} \sum_{k\ge 0} (-1)^{k} k z^k \; dz \\ = 2 (-1)^{n-q+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q+1}} (1+z)^{2n+1-q} \frac{z}{(1+z)^2} \; dz \\ = 2 (-1)^{n-q+1} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-q}} (1+z)^{2n-1-q} \; dz \\ = 2 (-1)^{n-q+1} {2n-1-q\choose n-q-1} = 2 (-1)^{n-q+1} {2n-1-q\choose n}.$$

We have the desired result if we can show that

$$\frac{q}{n} {2n-1-q\choose n-1} = {2n-q\choose n} - 2{2n-1-q\choose n}.$$

The right is $$\frac{2n-q}{n} {2n-1-q\choose n-1} - \frac{2(n-q)}{n} {2n-1-q\choose n-1}.$$

The claim now follows by inspection.

• I'd been reading your collected notes on Egorychev-style problems from this site and knew there had to be a way to do it! This is quite impressive, thank you. – sourisse Dec 2 '15 at 0:03
• Thank you, that is kind indeed. We might see a solution yet that does not require quite as much algebra as what I have above. I always treasure eureka moments. – Marko Riedel Dec 2 '15 at 0:11
• I guess the moral of the story is to reduce the problem to one coefficient of $v$ at a time. And, while a short solution is always satisfying, the integrals arising from Egorychev's method allowed me to derive asymptotics for the sum with a stationary phase argument rather than a messier power series argument. So it was a worthwhile tradeoff :) – sourisse Dec 2 '15 at 0:32