I am reading a paper and I am trying to understand an equality which is given without proof:
$$\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} $$
Here, $s>0$, $k$ and $v$ are positive integers.
The equality in question appears in Lemma 2.1 of
<http://web.williams.edu/Mathematics/sjmiller/public_html/ntharm15/handouts/graphs/mckay_EigenvalueLargeRandomGraphs.pdf>


Would you be kind and give me some insights on how to derive this equality?


Thank you,


LH



Equality with binomials
Here is a non-automated proof. We divide by $v$, and then we expand $v^{k-1}$ on the left hand side as
$$v^{k-1}=(1+v-1)^{k-1}=\sum\_{j=0}^{k-1}\binom{k-1}{j}(v-1)^j.$$
Then, looking at the coefficients of $v-1$ on the two sides, we are left with proving the identity
$$ \sum\_{\substack{0\leq k\leq s\\0\leq j\leq k-1\\j+s-k=\ell}}\binom{2s-k}{s}\frac{k}{2s-k}\binom{k-1}{j} = \binom{2s}{\ell}\frac{s-\ell}{s},\qquad 0\leq\ell\leq s-1.$$
With the notation $m:=s-k$ we have $k=s-m$, $j=\ell-m$, and the identity becomes
$$ \sum\_{m=0}^\ell\binom{s+m}{s}\frac{s-m}{s+m}\binom{s-m-1}{\ell-m} = \binom{2s}{\ell}\frac{s-\ell}{s},\qquad 0\leq\ell\leq s-1.$$
Equivalently,
$$ \sum\_{m=0}^\ell\binom{s+m-1}{s-1}\binom{s-m}{\ell-m} = \binom{2s}{\ell},\qquad 0\leq\ell\leq s-1, \tag3$$
i.e.,
$$ \sum\_{m=0}^\ell\binom{s+m-1}{s-1}\binom{s-m}{s-\ell} = \binom{2s}{2s-\ell},\qquad 0\leq\ell\leq s-1.$$
We derive this one from the obvious identity of analytic functions
$$ (1-x)^{-s}(1-x)^{\ell-s-1}=(1-x)^{\ell-2s-1},\qquad |x|<1.$$
Indeed, expanding each factor as a power series around the origin, we find that:


* the coefficient of $x^m$ in $(1-x)^{-s}$ equals $\binom{s+m-1}{s-1}$;
* the coefficient of $x^{\ell-m}$ in $(1-x)^{\ell-s-1}$ equals $\binom{s-m}{s-\ell}$;
* the coefficient of $x^{\ell}$ in $(1-x)^{\ell-2s-1}$ equals $\binom{2s}{2s-\ell}$.


