Equality with binomials

Question

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

Answer 1

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}$.

Answer 2

Let's re-index the sum on the LHS of the problem (for the below convenience) so that $$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-k}(v-1)^k =\frac{v}s\sum_{k=0}^{s-1}\binom{2s}k(s-k)(v-1)^k.$$ Or, just pull out the $v$ factor (leaving behind $\frac1s$, again for convenience): $$\frac1s\sum_{k=0}^{s-1}\binom{s+k-1}k(s-k)v^{s-1-k}(v-1)^k =\frac1s\sum_{k=0}^{s-1}\binom{2s}k(s-k)(v-1)^k.\tag1$$

We apply an automated technique called the Wilf-Zeilberger method for which Zeilberger wrote an algorithm, now implemented in symbolic softwares such as Maple and Mathematica.

To prove the above identity, we show both sides of (1) satisfy the same non-homogeneous recurrence $x(s+1)-v^2x(s)=\binom{2s}{s+1}\frac{(v-1)^{s+1}}s$ and just check one initial condition, say at $s=1$.

Suppressing other variables, let $F_1(s,k)=\binom{s+k-1}k\frac{s-k}sv^{s-1-k}(v-1)^k$ and $F_2(s,k)=\binom{2s}k\frac{s-k}s(v-1)^k$. The above method generates the WZ-mates \begin{align} G_1(s,k)&=F_1(s,k) \frac{v^2(s+2-k)k}{(s-k)(s+1)}, \\ G_2(s,k)&=F_2(s,k) \frac{(2s^2v+4sv+2s^2+3s-3svk-3kv+2v-2sk+vk^2)k}{(2s-k+1)(2s+2-k)(s-k)} \end{align} satisfying the relations (check using a computer) \begin{align} F_1(s+1,k)-v^2F_1(s,k)&=G_1(s,k+1)-G_1(s,k), \\ F_2(s+1,k)-v^2F_2(s,k)&=G_2(s,k+1)-G_2(s,k). \tag2 \end{align} Denote $a(s)=\sum_{k=0}^{s-1}F_1(s,k)$ and $b(s)=\sum_{k=0}^{s-1}F_2(s,k)$. Now, sum both equations in (2) over integers $0\leq k\leq s$. For instance, the first equation in (2) gives $$a(s+1)-v^2a(s)-v^2F_1(s,s)=G_1(s,s+1)-G_1(s,0).$$ But, $F_1(s,s)=0=G_1(s,0)$ and hence $a(s+1)-v^2a(s)=G_1(s,s+1)$.

Similarly, the second equation in (2) leads to $$b(s+1)-v^2b(s)-v^2F_2(s,s)=G_2(s,s+1)-G_2(s,0).$$ But, $F_2(s,s)=0=G_2(s,0)$ and hence $b(s+1)-v^2b(s)=G_2(s,s+1)$.

However, after some algebraic simplification, we obtain $$G_1(s,s+1)=G_2(s,s+1)=\binom{2s}{s+1}\frac{(v-1)^{s+1}}s.$$ Since $a(1)=b(1)$, it follows that $a(s)=b(s)$. The proof is complete.

Answer 3

This is not an answer but just some hints. Define $A(s)$ to be the quantity on the left and $B(s)$ to be the quantity on the right. Define $A(0)=B(0)=1$. Then it suffices to prove that $$ \sum_{s\ge0} A(s)x^s = \sum_{s\ge0} B(s)x^s = \frac{v-2-v\sqrt{1-4(v-1)x}}{2(v^2x-1)}.$$ Another way to prove it is to show that both $A(s)$ and $B(s)$ count the closed walks of length $2s$ in an infinite regular tree of degree $v$, which is the original application.