# (Combinatorial) proof of an identity of McKay

Lemma 2.1 of this paper claims that for integer $s>0$ and $v \in \mathbb{N}$, we have $$\sum_{k=1}^s \binom{2s-k}{s} \frac{k}{2s-k} v^k (v-1)^{s-k} = v \sum_{k=0}^{s-1} \binom{2s}{k} \frac{s-k}{s} (v-1)^k$$ The author gives a combinatorial interpretation of the left hand side in terms of closed walks on a class of graphs that are locally acyclic in a particular sense, but omits the proof of equality. I've hit a wall trying to prove this, so I was wondering what ideas others have. Combinatorial proofs welcomed!

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

Now the LHS is $$\frac{1}{n}\sum_{k=1}^n {2n-k-1\choose n-1} k v^k (v-1)^{n-k}.$$

Re-write this as $$\frac{1}{n}\sum_{k=1}^n {2n-k-1\choose n-k} k v^k (v-1)^{n-k}.$$

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

Observe that this zero when $k\gt n$ so we may extend $k$ to infinity to obtain for the sum $$\frac{1}{n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} (1+w)^{2n-1} \sum_{k\ge 1} k v^k (v-1)^{n-k} \frac{w^k}{(1+w)^k}\; dw \\ = \frac{(v-1)^n}{n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} (1+w)^{2n-1} \frac{vw/(v-1)/(1+w)}{(1-vw/(v-1)/(1+w))^2} \; dw \\ = \frac{(v-1)^n}{n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} (1+w)^{2n} \frac{vw(v-1)}{((v-1)(1+w)-vw)^2} \; dw \\ = v\frac{(v-1)^{n+1}}{n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n}} (1+w)^{2n} \frac{1}{(-1-w+v)^2} \; dw \\ = v\frac{(v-1)^{n-1}}{n} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n}} (1+w)^{2n} \frac{1}{(1-w/(v-1))^2} \; dw.$$

Extracting the coefficient we obtain $$v\frac{(v-1)^{n-1}}{n} \sum_{q=0}^{n-1} {2n\choose q} \frac{(n-1-q+1)}{(v-1)^{n-1-q}} \\ = v \sum_{q=0}^{n-1} {2n\choose q} \frac{(n-1-q+1)}{n} (v-1)^q \\ = v \sum_{q=0}^{n-1} {2n\choose q} \frac{(n-q)}{n} (v-1)^q.$$

This concludes the argument.

• Thank you, this technique seems quite useful. Do you know of any good references that elaborate on it? – sourisse Oct 29 '15 at 0:12
• The following MSE link contains a basic example, some references and additional links to auxiliary material. – Marko Riedel Oct 29 '15 at 1:10
• Great, thanks! I'm just going to wait a day or so to see if anyone can produce a combinatorial proof, but otherwise the bounty is yours! – sourisse Oct 29 '15 at 2:59
• Thanks. I forgot to mention, apparently this is known as the Egorychev method. – Marko Riedel Oct 29 '15 at 12:20