Another (complicated?) summation identity with binomial coefficients

Question

I posted this question a few weeks ago in hopes of being able to tackle the below questions. A follow up question is here.

I have tested the following identities for various numbers so I'm 99% sure they're correct. I will write it in the form @user355705 used in answering my original question.

The LHS for the odd and even part is the same. The difference between the first pair of identities and second pair is just the factor $\frac{1}{k}$ in the summation.

For even integers $0\leq g,h \leq N$, $$ \sum_{k\geq 1} \frac{4^k {(N-g)/2\choose k}{(N-h)/2\choose k}}{{N\choose 2k}{2k\choose k}} = \frac{N-g-h}{g+h+1}+ \frac{N+1}{g+h+1}\sum_{k\geq 1} \frac{4^k{g/2\choose k}{h/2\choose k}{(g+h)/2 \choose k}}{{N/2\choose k}{g+h\choose 2k}{2k\choose k}}$$

For odd integers $0< g,h \leq N$, $$ \sum_{k\geq 1} \frac{4^k {(N-g)/2\choose k}{(N-h)/2\choose k}}{{N\choose 2k}{2k\choose k}} = \frac{N+1-g-h}{g+h+1}+ \frac{N+2}{g+h+1}\sum_{k\geq 1} \frac{4^k{(g-1)/2\choose k}{(h-1)/2\choose k}{(g+h)/2 \choose k}}{{(N-1)/2\choose k}{g+h\choose 2k}{2k\choose k}}$$

The question posted here was the below for $g=0$.

For even integers $0\leq g,h \leq N$, $$ \sum_{k\geq 1} \frac{1}{k}\frac{4^k {(N-g)/2\choose k}{(N-h)/2\choose k}}{{N\choose 2k}{2k\choose k}} = \sum_{j=1}^{(N-g-h)/2} \frac{2}{2j+g+h-1}+ \sum_{k\geq 1} \frac{1}{k}\frac{4^k{g/2\choose k}{h/2\choose k}{(g+h)/2 \choose k}}{{N/2\choose k}{g+h\choose 2k}{2k\choose k}}$$

For odd integers $1<g,h \leq N$, $$ \sum_{k\geq 1} \frac{1}{k}\frac{4^k {(N-g)/2\choose k}{(N-h)/2\choose k}}{{N\choose 2k}{2k\choose k}} = \sum_{j=1}^{(N+1-g-h)/2} \frac{2}{2j+g+h-1}+ \sum_{k\geq 1} \frac{1}{k}\frac{4^k{(g-1)/2\choose k}{(h-1)/2\choose k}{(g+h)/2 \choose k}}{{(N-1)/2\choose k}{g+h\choose 2k}{2k\choose k}}$$

I'm not happy how I had to split it up into odd and even cases. I could combine the statements with the use of floor and ceiling functions but that seemed unnatural.

Any tips or help would be appreciated.

Answer 1

The great simplification of the problem performed by Markus Scheuer allows the proof of his last equation by induction. In what follows $z$ means the complex number $\alpha-1$ introduced by Markus.

First of all we simplify the expression a bit further including the summation over $k=0$ as well: $$ S(M,G,H,z):=\sum_{k\ge0}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M+z}{k}}= \frac{M+z+1}{G+H+z+1}\sum_{k\ge0}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H+z}{k}}.\tag{1} $$ In what follows we assume $M\ge G,H\ge0$, $z+1\not\in\{-\max(M,G+H),\dots,-\max(G,H)\}$, so that both sides of the equation (1) are finite. As the expression is symmetric with respect to $G$ and $H$ we may without loss of generality assume $G\ge H$.

Assume $M=G$. The expression (1) for $S(G,G,H,z)$ will read: $$ 1=\frac{G+z+1}{G+H+z+1}\sum_{k\ge0}\frac{\binom{H}{k}}{\binom{G+H+z}{k}} \Leftrightarrow \sum_{k\ge0}\frac{\binom{H}{k}}{\binom{G+H+z}{k}}=\frac{G+H+z+1}{G+z+1},\tag{2} $$ which is a valid equality proved earlier (equation (*) with $z_1=H$ and $z_2=G+H+z+1$).

Now we prove by induction that if equation (1) is valid for $M'<M$ it is valid for $M$ as well. $$ S(M,G,H,z)=\sum_{k\ge0}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M+z}{k}}=1+ \sum_{k\ge1}\frac{\frac{M-G}{k}\binom{M-G-1}{k-1}\frac{M-H}{k}\binom{M-H-1}{k-1}}{\frac{M}{k}\binom{M-1}{k-1}\frac{M+z}{k}\binom{M+z-1}{k-1}}\\ =1+{\small\frac{(M-G)(M-H)}{M(M+z)}}\sum_{k\ge0}\frac{\binom{M-G-1}{k}\binom{M-H-1}{k}}{\binom{M-1}{k}\binom{M+z-1}{k}}\\ \stackrel{I.H.1}{=}1+{\small\frac{(M-G)(M-H)}{M(M+z)}\cdot\frac{M+z}{G+H+z+1}}\sum_{k\ge0}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M-1}{k}\binom{G+H+z}{k}}.\tag{3} $$ Next we compute $$ \sum_{k\ge0}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M-1}{k}\binom{G+H+z}{k}}= 1+{\small\frac{GH}{(M-1)(G+H+z)}}\sum_{k\ge0}\frac{\binom{G-1}{k}\binom{H-1}{k}}{\binom{M-2}{k}\binom{G+H+z-1}{k}}\\ \stackrel{I.H.2}{=} 1+{\small\frac{GH}{(M-1)(G+H+z)}\cdot\frac{G+H+z}{M+z}}\sum_{k\ge0}\frac{\binom{M-G-1}{k}\binom{M-H-1}{k}}{\binom{M-2}{k}\binom{M+z-1}{k}}.\tag{4} $$ Plugging (4) into (3) one obtains: $$ S(M,G,H,z)=1+{\small\frac{(M-G)(M-H)}{M(G+H+z+1)}}\left(1+{\small\frac{GH}{(M-1)(M+z)}}\sum_{k\ge0}\frac{\binom{M-G-1}{k}\binom{M-H-1}{k}}{\binom{M-2}{k}\binom{M+z-1}{k}}\right)\\ =1+{\small\frac{(M-G)(M-H)}{M(G+H+z+1)}}+{\small\frac{GH}{M(G+H+z+1)}}\sum_{k\ge0}\frac{\binom{M-G}{k+1}\binom{M-H}{k+1}}{\binom{M-1}{k+1}\binom{M+z}{k+1}}\\ 1+{\small\frac{(M-G)(M-H)}{M(G+H+z+1)}}+{\small\frac{GH}{M(G+H+z+1)}}\left(\sum_{k\ge0}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M-1}{k}\binom{M+z}{k}}-1\right)\\ ={\small\frac{M+z+1}{G+H+z+1}}+{\small\frac{GH}{M(G+H+z+1)}}\sum_{k\ge0}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M-1}{k}\binom{M+z}{k}}\\ \stackrel{I.H.3}{=} {\small\frac{M+z+1}{G+H+z+1}}+{\small\frac{GH}{M(G+H+z+1)}\cdot\frac{M+z+1}{G+H+z}}\sum_{k\ge0}\frac{\binom{G-1}{k}\binom{H-1}{k}}{\binom{M-1}{k}\binom{G+H+z-1}{k}}\\ ={\small\frac{M+z+1}{G+H+z+1}}+{\small\frac{M+z+1}{G+H+z+1}}\sum_{k\ge0}\frac{\binom{G}{k+1}\binom{H}{k+1}}{\binom{M}{k+1}\binom{G+H+z}{k+1}}\\ ={\small\frac{M+z+1}{G+H+z+1}}\sum_{k\ge0}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H+z}{k}},\tag{5} $$ as claimed.

The following sums were transformed in accord with the induction hypothesis: $$ \begin{align} I.H.1:&\quad S(M-1,G,H,z),\\ I.H.2:&\quad S(M-2,G-1,H-1,z+1),\\ I.H.3:&\quad S(M-1,G-1,H-1,z+1), \end{align} $$ which suggests that the cases $H=0$, $M=0$, $M=1$ require a separate treatment.

As easily seen for $H=0$ the equation (1) reduces to: $$ S(M,G,0,z)=\sum_{k\ge0}\frac{\binom{M-G}{k}}{\binom{M+z}{k}}= \frac{M+z+1}{G+z+1},\tag{6} $$ which is again valid equality (*) with $z_1=M-G$ and $z_2=M+z+1$.

The cases $M=0$ and $M=1$ are covered by at least one of equalities (2) and (6).

Thus the equality $$ \frac{1}{M+\alpha}\sum_{k\ge0}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M+\alpha-1}{k}}= \frac{1}{G+H+\alpha}\sum_{k\ge0}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H+\alpha-1}{k}}\tag{7} $$ is proved for all integer $M\ge G,H\ge0$ and for all $\alpha\in\mathbb{C}\setminus\{-\max(M,G+H),\dots,-\max(G,H)\}$.

A more thoughtful analysis reveals that actual singularities of $f_{MGH}(z)=\frac{S(M,G,H,z-1)}{M+z}$ are simple poles at integer values in the range $\{-\min(M,G+H),\dots,-\max(G,H)\}$. The other singularities in the range $\{-\max(M,G+H),\dots,-\min(M,G+H)-1\}$ are removable.

Answer 2

We simplify the expressions and parametrise them to get one formula for even and odd case. In fact it seems the so derived identity can be generalised even more.

Here we focus on the first even/odd pair of the (claimed) identities. The second one can be treated analogously.

Even case:

It is convenient to put $N=2M, g=2G, h=2H$. This way the identity becomes for non-negative integer $0\leq G,H\leq M$ and $M\geq 1$: \begin{align*} \sum_{k\geq 1}4^k\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{2M}{2k}\binom{2k}{k}} &=\frac{M-G-H}{G+H+\frac{1}{2}}\\ &\qquad+\frac{M+\frac{1}{2}}{G+H+\frac{1}{2}}\sum_{k\geq 1}4^k\frac{\binom{G}{k}\binom{H}{k}\binom{G+H}{k}}{\binom{M}{k}\binom{2G+2H}{2k}\binom{2k}{k}}\tag{1} \end{align*}

The series of the LHS in (1) is \begin{align*} \color{blue}{\sum_{k\geq 1}}&\color{blue}{4^k\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{2M}{2k}\binom{2k}{k}}}\\ &=\sum_{k\geq 1}4^k\frac{(M-G)^{\underline{k}}}{k!}\cdot\frac{(M-H)^{\underline{k}}}{k!}\cdot \frac{(2k)!}{(2M)^{\underline{2k}}}\cdot\frac{k!k!}{(2k)!}\tag{2}\\ &=\sum_{k\geq 1}4^k\frac{(M-G)^{\underline{k}}(M-H)^{\underline{k}}}{2^{2k}M^{\underline{k}}\left(M-\frac{1}{2}\right)^{\underline{k}}}\tag{3}\\ &=\sum_{k\geq 1}\frac{(M-G)^{\underline{k}}(M-H)^{\underline{k}}}{M^{\underline{k}}\left(M-\frac{1}{2}\right)^{\underline{k}}}\\ &\color{blue}{=\sum_{k\geq 1}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M-\frac{1}{2}}{k}}}\tag{4} \end{align*}

Comment:

• In (2) we use the falling factorial $n^{\underline{k}}=n(n-1)\cdots (n-k+1)$.

• In (3) we use the identity $(2M)^{\underline{2k}}=2^{2k}M^{\underline{k}}\left(M-\frac{1}{2}\right)^{\underline{k}}$ and do some simplifications.

• In (4) we use the representation $\binom{n}{k}=\frac{n^{\underline{k}}}{k!}$.

The series of the RHS in (1) is \begin{align*} \color{blue}{\sum_{k\geq 1}}&\color{blue}{4^k\frac{\binom{G}{k}\binom{H}{k}\binom{G+H}{k}}{\binom{M}{k}\binom{2G+2H}{2k}\binom{2k}{k}}}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}}{k!}\cdot \frac{H^{\underline{k}}}{k!}\cdot\frac{(G+H)^{\underline{k}}}{k!} \cdot\frac{k!}{M^{\underline{k}}}\cdot\frac{(2k)!}{(2G+2H)^{\underline{2k}}}\cdot\frac{k!k!}{(2k)!}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}H^{\underline{k}}(G+H)^{\underline{k}}}{M^{\underline{k}}(2G+2H)^{\underline{2k}}}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}H^{\underline{k}}(G+H)^{\underline{k}}}{M^{\underline{k}}2^{2k}(G+H)^{\underline{k}}\left(G+H-\frac{1}{2}\right)^{\underline{k}}}\\ &=\sum_{k\geq 1}\frac{G^{\underline{k}}H^{\underline{k}}}{M^{\underline{k}}\left(G+H-\frac{1}{2}\right)^{\underline{k}}}\\ &\color{blue}{=\sum_{k\geq 1}{\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H-\frac{1}{2}}{k}}}}\tag{5} \end{align*}

Using (4) and (5) in (1) we obtain:

The following is valid for non-negative integer $0\leq G,H\leq M$ and $M\geq 1$: \begin{align*} \sum_{k\geq 1}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M\color{blue}{-\frac{1}{2}}}{k}} &=\frac{M-G-H}{G+H\color{blue}{+\frac{1}{2}}} +\frac{M\color{blue}{+\frac{1}{2}}}{G+H\color{blue}{+\frac{1}{2}}}\sum_{k\geq 1}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H\color{blue}{-\frac{1}{2}}}{k}}\tag{6} \end{align*}

Odd case:

We put $N=2M+1, g=2G+1, h=2H+1$ and obtain \begin{align*} \sum_{k\geq 1}4^k\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{2M+1}{2k}\binom{2k}{k}}& =\frac{M-G-H}{G+H+\frac{3}{2}}\\ &\qquad +\frac{M+\frac{3}{2}}{G+H+\frac{3}{2}}\sum_{k\geq 1}4^k\frac{\binom{G}{k}\binom{H}{k}\binom{G+H+1}{k}}{\binom{M}{k}\binom{2G+2H+2}{2k}\binom{2k}{k}}\tag{7} \end{align*}

The series of the LHS in (7) is \begin{align*} \color{blue}{\sum_{k\geq 1}}&\color{blue}{4^k\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{2M+1}{2k}\binom{2k}{k}}}\\ &=\sum_{k\geq 1}4^k\frac{(M-G)^{\underline{k}}}{k!}\cdot\frac{(M-H)^{\underline{k}}}{k!}\cdot \frac{(2k)!}{(2M+1)^{\underline{2k}}}\cdot\frac{k!k!}{(2k)!}\\ &=\sum_{k\geq 1}4^k\frac{(M-G)^{\underline{k}}(M-H)^{\underline{k}}}{2^{2k}M^{\underline{k}}\left(M+\frac{1}{2}\right)^{\underline{k}}}\\ &=\sum_{k\geq 1}\frac{(M-G)^{\underline{k}}(M-H)^{\underline{k}}}{M^{\underline{k}}\left(M+\frac{1}{2}\right)^{\underline{k}}}\\ &\color{blue}{=\sum_{k\geq 1}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M+\frac{1}{2}}{k}}}\tag{8} \end{align*}

The series of the RHS in (7) is \begin{align*} \color{blue}{\sum_{k\geq 1}}&\color{blue}{4^k\frac{\binom{G}{k}\binom{H}{k}\binom{G+H+1}{k}}{\binom{M}{k}\binom{2G+2H+2}{2k}\binom{2k}{k}}}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}}{k!}\cdot \frac{H^{\underline{k}}}{k!}\cdot\frac{(G+H+1)^{\underline{k}}}{k!} \cdot\frac{k!}{M^{\underline{k}}}\cdot\frac{(2k)!}{(2G+2H+2)^{\underline{2k}}}\cdot\frac{k!k!}{(2k)!}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}H^{\underline{k}}(G+H+1)^{\underline{k}}}{M^{\underline{k}}(2G+2H+2)^{\underline{2k}}}\\ &=\sum_{k\geq 1}4^k\frac{G^{\underline{k}}H^{\underline{k}}(G+H+1)^{\underline{k}}}{M^{\underline{k}}2^{2k}(G+H+1)^{\underline{k}}\left(G+H+\frac{1}{2}\right)^{\underline{k}}}\\ &=\sum_{k\geq 1}\frac{G^{\underline{k}}H^{\underline{k}}}{M^{\underline{k}}\left(G+H+\frac{1}{2}\right)^{\underline{k}}}\\ &\color{blue}{=\sum_{k\geq 1}{\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H+\frac{1}{2}}{k}}}}\tag{9} \end{align*}

Using (8) and (9) we obtain a formula corresponding to (6)

\begin{align*} \sum_{k\geq 1}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M\color{blue}{+\frac{1}{2}}}{k}} =\frac{M-G-H}{G+H\color{blue}{+\frac{3}{2}}}+\frac{M\color{blue}{+\frac{3}{2}}}{G+H\color{blue}{+\frac{3}{2}}}\sum_{k\geq 1}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H\color{blue}{+\frac{1}{2}}}{k}}\tag{10} \end{align*}

Parametrisation:

We can now conveniently represent the even case (6) and the odd case (10) by parametrising them with let's say $\alpha\in\{0,1\}$. In fact it seems that even more is valid and we claim (shifting $\alpha$ by $1/2$):

The following is valid for non-negative integer $0\leq G,H\leq M$, $M\geq 1$ and for all $\alpha\in\mathbb{C}\setminus\{-G-H\}$: \begin{align*} \color{blue}{\sum_{k\geq 1}\frac{\binom{M-G}{k}\binom{M-H}{k}}{\binom{M}{k}\binom{M-1+\alpha}{k}}}&\color{blue}{ =\frac{M-G-H}{G+H+\alpha}} \color{blue}{+\frac{M+\alpha}{G+H+\alpha}\sum_{k\geq 1}\frac{\binom{G}{k}\binom{H}{k}}{\binom{M}{k}\binom{G+H-1+\alpha}{k}}} \end{align*} Note that both sides coincide when $M=G+H$.

The other pair of identities with additional factor $\frac{1}{k}$ can be treated similarly.

Answer 3

The expression can probably not be simplified beyond a sum over 4 binomial coefficients: \begin{equation} \sum_k 4^k\frac{\binom{N/2-g/2}{k} \binom{N/2-h/2}{k}} {\binom{N}{2k}\binom{2k}{k}} \end{equation} \begin{equation} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)} \sum_k 4^k\frac{\Gamma(N-2k+1)}{\Gamma(N/2-g/2-k+1\Gamma(N/2-h/2-k+1)} \end{equation} and by the $\Gamma$-duplication formula \begin{equation} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)\sqrt{2\pi}} \sum_k 4^k\frac{\Gamma(N/2-k+1/2)\Gamma(N/2-k+1)2^{N-2k+1/2}}{\Gamma(N/2-g/2-k+1\Gamma(N/2-h/2-k+1)} \end{equation} \begin{multline} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)\sqrt{2\pi}} 2^{N+1/2} \\ \times \sum_k \frac{\Gamma(N/2-k+1/2)\Gamma(N/2-k+1)\Gamma(k+1)} {\Gamma(N/2-g/2-k+1\Gamma(N/2-h/2-k+1)k!} \end{multline} \begin{multline} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)\sqrt{2\pi}} 2^{N+1/2}\\ \times \sum_k \frac{\Gamma(N/2+1/2)\Gamma(N/2+1)(g/2-N/2)_k(h/2-N/2)_k\Gamma(k+1)} {\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)(1/2-N/2)_k(-N/2)_kk!} \end{multline} \begin{multline} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)\sqrt{\pi}} 2^N \frac{\Gamma(N/2+1/2)\Gamma(N/2+1)} {\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)} \\ \times \sum_k \frac{(g/2-N/2)_k(h/2-N/2)_k\Gamma(k+1)} {(1/2-N/2)_k(-N/2)_kk!} \end{multline} \begin{multline} = \frac{\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)}{\Gamma(N+1)\sqrt{\pi}} 2^N \frac{\Gamma(N/2+1/2)\Gamma(N/2+1)} {\Gamma(N/2-g/2+1)\Gamma(N/2-h/2+1)} \\ \times {}_3F_2(g/2-N/2,h/2-N/2,1; 1/2-N/2,-N/2;1) \end{multline} \begin{multline} = \frac{1}{\Gamma(N+1)\sqrt{\pi}} 2^N \Gamma(N/2+1/2)\Gamma(N/2+1) \\ \times {}_3F_2(g/2-N/2,h/2-N/2,1; 1/2-N/2,-N/2;1) \end{multline} \begin{multline} = \frac{\sqrt{2}}{\Gamma(N/2+1/2)\Gamma(N/2+1)2^{1/2}} \Gamma(N/2+1/2)\Gamma(N/2+1) \\ \times {}_3F_2(g/2-N/2,h/2-N/2,1; 1/2-N/2,-N/2;1) \end{multline} \begin{equation} = {}_3F_2(g/2-N/2,h/2-N/2,1; 1/2-N/2,-N/2;1) \end{equation} \begin{equation} =\sum_k \frac{(g/2-N/2)_k(h/2-N/2)_k}{(1/2-N/2)_k(-N/2)_k} \end{equation}