Proof of (complicated?) summation equality

Question

This is a simplified case of something I'm trying to prove.

Suppose that $N,h$ are even. I want to show that $$ \sum_{k=1}^{(N-h)/2} \frac{2^{2k}}{kN^{\underline{2k}}}\left(\frac{N}{2}\right)^{\underline{k}}\left(\frac{N-h}{2}\right)^{\underline{k}} = \sum_{j=1}^{(N-h)/2} \frac{2}{2j+h-1} $$ where $n^{\underline{k}} = n(n-1)...(n-k+1)$ is the falling factorial. Now the LHS terms can be written as follows

\begin{align} \frac{2^{2k}}{kN^{\underline{2k}}}\left(\frac{N}{2}\right)^{\underline{k}}\left(\frac{N-h}{2}\right)^{\underline{k}} &= \frac{1}{kN^{\underline{2k}}} \prod_{j=0}^{k-1} (N-2j)(N-h-2j) \\&= \frac{1}{k} \prod_{j=0}^{k-1} \frac{N-h-2j}{N-2j-1} \\&= \frac{1}{k} \prod_{j=0}^{k-1} \left(1-\frac{h-1}{N-2j-1}\right). \end{align} Note the RHS can be written as $H_{\frac{N}{2}-\frac{1}{2}}-H_{\frac{h}{2}-\frac{1}{2}}$ where $H_n$ is the Harmonic number.

Answer 1

Since you've already got $$\frac{2^{2k}}{kN^{\underline{2k}}}\left(\frac{N}{2}\right)^{\underline{k}}\left(\frac{N-h}{2}\right)^{\underline{k}}= \frac{1}{k} \prod_{j=0}^{k-1} \frac{N-h-2j}{N-2j-1}$$

let us prove by induction on $m$ where $N=h+2m$ that $$\sum_{j=1}^{m} \frac{2}{2j+h-1}=\sum_{k=1}^{m} \frac{1}{k} \prod_{j=0}^{k-1} \frac{2m-2j}{h+2m-2j-1} \tag1$$

For $m=1$, $(1)$ holds since the both sides of $(1)$ equal $\frac{2}{h+1}$.

Suppose that $(1)$ holds for some $m\ (\ge 1)$.

Then, $$\small\begin{align}&\sum_{j=1}^{m+1} \frac{2}{2j+h-1}\\\\&\stackrel{I.H.} =\frac{2}{2(m+1)+h-1}+\sum_{k=1}^{m} \frac{1}{k}\cdot \underbrace{\prod_{j=0}^{k-1} \frac{2m-2j}{h+2m-2j-1}}_{A} \\\\&=\frac{2}{h+2m+1}+\sum_{k=1}^{m} \frac 1k\cdot\underbrace{\frac{(h+2m+1)(2m+2-2k)}{(2m+2)(h+2m-2k+1)}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} }_{A} \\\\&=\frac{2}{h+2m+1}+\sum_{k=1}^{m} \frac 1k\cdot \underbrace{\frac{(h+2m+1)(2m+2-2k)}{(2m+2)(h+2m-2k+1)}}_{B}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&=\frac{2}{h+2m+1}+\sum_{k=1}^{m}\frac 1k\cdot\underbrace{\left(1-\frac{k(h-1)}{(m+1)(h+2m-2k+1)}\right)}_{B}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&=\frac{2}{h+2m+1}+\underbrace{\sum_{k=1}^{m}\frac 1k\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}}_{C} \\\\&\qquad\quad -\frac{h-1}{m+1}\sum_{k=1}^{m}\frac{1}{h+2m-2k+1}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&=\frac{2}{h+2m+1}+\underbrace{\left(\sum_{k=1}^{m+1}\frac 1k\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}\right)-\frac{1}{m+1}\prod_{j=0}^{m}\frac{2m+2-2j}{h+2m-2j+1}}_{C} \\\\&\qquad\quad -\frac{h-1}{m+1}\sum_{k=1}^{m}\frac{1}{h+2m-2k+1}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&=\frac{2}{h+2m+1}+\sum_{k=1}^{m+1}\frac 1k\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&\qquad\quad \underbrace{-\frac{1}{m+1}\prod_{j=0}^{m}\frac{2m+2-2j}{h+2m-2j+1}-\frac{h-1}{m+1}\sum_{k=1}^{m}\frac{1}{h+2m-2k+1}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}}_{D} \\\\&=\frac{2}{h+2m+1}+\sum_{k=1}^{m+1}\frac 1k\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1} \\\\&\qquad\quad \underbrace{-\frac{h-1}{m+1}\sum_{k=1}^{m+1}\frac{1}{h+2m-2k+1}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}}_{D} \\\\&=\sum_{k=1}^{m+1}\frac 1k\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}\qquad\blacksquare\end{align}$$

---

The last equality comes from that $$\frac{h-1}{m+1}\sum_{k=1}^{m+1}\frac{1}{h+2m-2k+1}\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}=\frac{2}{h+2m+1}\tag2$$

Finally, let us prove $(2)$ using a telescoping sum.

Let $$f(k):=\prod_{j=0}^{k-1} \frac{2(m+1)-2j}{h+2(m+1)-2j-1}$$

The key is $$\frac{f(k)}{h+2m-2k+1}=\frac{1}{1-h}\left(f(k+1)-f(k)\right)\tag3$$ which holds since $$\begin{align}f(k+1)-f(k)&=f(k)\left(\frac{2(m+1)-2k}{h+2(m+1)-2k-1}-1\right)\\\\&=\frac{f(k)}{h+2m-2k+1}(2m+2-2k-(h+2m-2k+1))\\\\&=\frac{f(k)}{h+2m-2k+1}(1-h)\end{align}$$ Using $(3)$, we have $$\begin{align}\frac{h-1}{m+1}\sum_{k=1}^{m+1}\frac{f(k)}{h+2m-2k+1}&=\frac{h-1}{m+1}\sum_{k=1}^{m+1}\frac{1}{1-h}\left(f(k+1)-f(k)\right)\\\\&=-\frac{1}{m+1}\sum_{k=1}^{m+1}\left(f(k+1)-f(k)\right)\\\\&=-\frac{1}{m+1}(f(m+2)-f(1))\\\\&=-\frac{1}{m+1}\left(0-\frac{2(m+1)}{h+2(m+1)-1}\right)\\\\&=\frac{2}{h+2m+1}\qquad\blacksquare\end{align}$$

Answer 2

Consider the sum $$ S^n_m=\sum_{k=1}^m4^k\frac{\binom{n}{k}\binom{m}{k}}{\binom{2n}{2k}\binom{2k}{k}};\quad n\ge m\ge1.\tag{1} $$ We are going to prove: $$ S^n_m=\frac{2m}{2n-2m+1}.\tag{2} $$ It is easy to check that for $m=1$ and arbitrary $n\ge1$ the expression (2) is valid: $$ S^{n}_1=4^1\frac{\binom{n}{1}\binom{1}{1}}{\binom{2n}{2}\binom{2}{1}}=\frac{2}{2n-1}. $$

Assume that expression (2) is valid for some $S^{n-1}_{m-1}$ $(n\ge m\ge 2)$. It follows then that it is valid for $S^{n}_{m}$ as well: $$\begin {align} S^{n}_{m}&=\sum_{k=1}^{m}4^k\frac{\binom{n}{k}\binom{m}{k}}{\binom{2n}{2k}\binom{2k}{k}}\\ &=\sum_{k=1}^{m}4^k\frac{\frac{n}{k}\binom{n-1}{k-1}\frac{m}{k}\binom{m-1}{k-1}}{\frac{2n(2n-1)}{2k(2k-1)}\binom{2n-2}{2k-2}\frac{2k(2k-1)}{k^2}\binom{2k-2}{k-1}}\\ &=\frac{2m}{2n-1}\sum_{k=1}^{m}4^{k-1}\frac{\binom{n-1}{k-1}\binom{m-1}{k-1}}{\binom{2n-2}{2k-2}\binom{2k-2}{k-1}}\\ &=\frac{2m}{2n-1}\sum_{k=0}^{m-1}4^{k}\frac{\binom{n-1}{k}\binom{m-1}{k}}{\binom{2n-2}{2k}\binom{2k}{k}}\\ & =\frac{2m}{2n-1}\left(S^{n-1}_{m-1}+1\right)\\ &\stackrel{I.H.}{=}\frac{2m}{2n-1}\left(\frac{2(m-1)}{2(n-1)-2(m-1)+1}+1\right)\\ & =\frac{2m}{2n-1}\cdot\frac{2n-1}{2n-2m+1}\\ &=\frac{2m}{2n-2m+1},\end {align} $$ where $\stackrel{I.H.}{=}$ means substitution of the induction assumption. Thus, the equality (2) is proved.

The rest is rather straightforward. Let $l$ be an integer number $(1\le l\le n)$. Then: $$\begin {align} \sum_{m=1}^l\frac{2}{2n-2m+1}&\stackrel {(2)}=\sum_{m=1}^l\frac{1}{m}\sum_{k=1}^m4^k\frac{\binom{n}{k}\binom{m}{k}}{\binom{2n}{2k}\binom{2k}{k}}\\ &= \sum_{m=1}^l\frac{1}{m}\sum_{k=1}^\infty4^k\frac{\binom{n}{k}\binom{m}{k}}{\binom{2n}{2k}\binom{2k}{k}}\\ &=\sum_{k=1}^\infty4^k\frac{\binom{n}{k}}{\binom{2n}{2k}\binom{2k}{k}}\sum_{m=1}^l\frac{1}{m}\binom{m}{k}\\ &\stackrel{!}{=}\sum_{k=1}^\infty\frac{4^k}{k}\frac{\binom{n}{k}\binom{l}{k}}{\binom{2n}{2k}\binom{2k}{k}}\\ &=\sum_{k=1}^l\frac{4^k}{k}\frac{\binom{n}{k}\binom{l}{k}}{\binom{2n}{2k}\binom{2k}{k}}.\tag{3}\end {align} $$

The proof of identity: $$ \sum_{m=1}^l\frac{1}{m}\binom{m}{k}=\frac{1}{k}\binom{l}{k};\quad k\ge1, $$ used in $\stackrel{!}{=}$, is left as an exercise.

The equality (3) is identical to that one claimed in question. To see it redefine in the latter $N=2n$, $h=2(n-l)$ and reverse the summation order in RHS: $j\mapsto l+1-j$.

Answer 3

To complement the nice answer provided by user355705, please refer to the answer provided in this related post where it is shown that $$ \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,m} {4^{\,k} {{\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ m \cr k \cr} \right)} \over {\left( \matrix{ 2n \cr 2k \cr} \right)\left( \matrix{ 2k \cr k \cr} \right)}}} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {{{\left( \matrix{ m \cr k \cr} \right)} \over {\left( \matrix{ n - 1/2 \cr k \cr} \right)}}} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr k \cr} \right)1^{\,\overline {\,k\,} } \left( {n + 1/2} \right)^{\,\overline {\, - \,k\,} } } \cr & = {1 \over {\left( {n - m + 1/2} \right)^{\,\overline {\,m\,} } }}\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr k \cr} \right)1^{\,\overline {\,k\,} } \left( {n - m + 1/2} \right)^{\,\overline {\,m - \,k\,} } } = \cr & = {{\left( {n - m + 3/2} \right)^{\,\overline {\,m\,} } } \over {\left( {n - m + 1/2} \right)^{\,\overline {\,m\,} } }} = {{n + 1/2} \over {n - m + 1/2}} = {{2n + 1} \over {2(n - m) + 1}} \cr} } $$

This identity is valid for any non-negative integer $m$, and for $n$ that can take even a real or complex value, except for $n=m-1/2$.
This under the acception that the two binomials in $n$, when null get simplified. That is that the two binomials be rewritten as above in terms of Falling Factorials (or Gamma function) with $n$ real, and simplify the fraction (take the limit).