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.

  • $\begingroup$ Thank you, this technique seems quite useful. Do you know of any good references that elaborate on it? $\endgroup$ – sourisse Oct 29 '15 at 0:12
  • $\begingroup$ The following MSE link contains a basic example, some references and additional links to auxiliary material. $\endgroup$ – Marko Riedel Oct 29 '15 at 1:10
  • $\begingroup$ 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! $\endgroup$ – sourisse Oct 29 '15 at 2:59
  • $\begingroup$ Thanks. I forgot to mention, apparently this is known as the Egorychev method. $\endgroup$ – Marko Riedel Oct 29 '15 at 12:20

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.