Hard binomial sum

Question

How to prove this relation? $$\sum_{i=0}^{n}\frac{2^{-2i}\binom{2i}{i}}{n+i+2}=\frac{2^{4n+2}-\binom{2n+1}{n}^2}{(2n+3)2^{2n+1}\binom{2n+1}{n}}$$ That seems difficult!

Answer 1

Note: The following answer is divided in three steps. We start with a short

Overview

Step 1: A convenient representation

We transform OPs expression by doing some index shifting and by adding one summand to both sides which considerably simplifies the RHS of OPs expression.

We show OPs expression is equivalent to \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{n+i}\frac{1}{2^{2i}}=2^{2n-1}\frac{1}{n}\binom{2n}{n}^{-1}\qquad n\geq 1\tag{1} \end{align*}

Let's denote the LHS of (1) with $A(n)$. We now start finding in

Step 2: A recurrence relation for $$A(n)=\sum_{i=0}^{n-1}\frac{1}{n+i}\frac{1}{2^{2i}}\binom{2i}{i}$$

We will show that \begin{align*} A(n)&=\frac{2n-2}{2n-1}A(n-1)\qquad\qquad n\geq 1\tag{2} \end{align*}

Together with $A(1)=1$ the claim (1) follows.

But in order to prove the recurrence relation (2) we have to show another binomial identity regarding Catalan numbers in an intermediate

Step 3: A nice binomial identity regarding Catalan numbers

The following is valid \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}}=2-\frac{1}{2^{2n-1}}\binom{2n}{n}\qquad\qquad n \geq 1\tag{3} \end{align*}

Note: Identity (3) is interesting. Writing $C_n=\binom{2n}{n}\frac{1}{n+1}$ for the $n$-th Catalan number we get a recurrence relation for $C_n$

\begin{align*} (n+1)\frac{C_n}{4^n}=1-\frac{1}{2}\sum_{i=0}^{n-1}\frac{C_i}{4^i}\qquad \qquad n\geq 0\tag{4} \end{align*} The recurrence relation (4) specifies all Catalan numbers starting from $C_0=1$ when using the convention that the empty sum ($n=0$) is zero.

Another nice aspect regarding (1) is that the LHS is the $(n-1)$-st order Taylor polynomial of the generating function \begin{align*} \frac{1-\sqrt{1-4z}}{2z}=\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{n+1}z^n\tag{5} \end{align*} of the Catalan numbers evaluated at $z=\frac{1}{4}$. The series converges uniformly in the open disc $|z|<\frac{1}{4}$ and it also converges at $z=\frac{1}{4}$. We obtain using the RHS of (3) and the generating function from (5): \begin{align*} \lim_{n\rightarrow\infty}\left(2-\frac{1}{2^{2n-1}}\binom{2n}{n}\right)=\left.\frac{1-\sqrt{1-4z}}{2z}\right|_{z=\frac{1}{4}}=2 \end{align*}

---

And now the gory details.

The following is to prove for $n\geq 0$ \begin{align*} \sum_{i=0}^{n}\binom{2i}{i}\frac{1}{n+i+2}\frac{1}{2^{2i}}=2^{2n+1}\frac{1}{2n+3}\binom{2n+1}{n}^{-1} -\frac{1}{2^{2n+1}}\frac{1}{2n+3}\binom{2n+1}{n} \end{align*}

$$$$

Step 1: A convenient representation

We substitute $n\rightarrow n-2$ in OPs expression and so we have to show for $n\geq 2$

\begin{align*} \sum_{i=0}^{n-2}\binom{2i}{i}\frac{1}{n+i}\frac{1}{2^{2i}}=2^{2n-3}\frac{1}{2n-1}\binom{2n-3}{n-2}^{-1} -\frac{1}{2^{2n-3}}\frac{1}{2n-1}\binom{2n-3}{n-2} \end{align*}

We add at both sides the term with $i=n-1$ and obtain for $n \geq 1$ \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{n+i}\frac{1}{2^{2i}}&=2^{2n-3}\frac{1}{2n-1}\binom{2n-3}{n-2}^{-1} -\frac{1}{2^{2n-3}}\frac{1}{2n-1}\binom{2n-3}{n-2}\\ &\qquad+\frac{1}{2^{2n-2}}\frac{1}{2n-1}\binom{2n-2}{n-1}\tag{6}\\ &=2^{2n-3}\frac{1}{2n-1}\binom{2n-3}{n-2}^{-1}\tag{7}\\ &=2^{2n-1}\frac{1}{n}\binom{2n}{n}^{-1} \end{align*}

and (1) follows.

Comment:

• In (6) we use $\binom{2n-2}{n-1}=\binom{2n-3}{n-2}\frac{2n-2}{n-1}=2\binom{2n-3}{n-2}$

• In (7) we proceed similar to (6) and also use $\binom{2n-1}{n}=\frac{1}{2}\binom{2n}{n}$

Step 2: A recurrence relation for $A(n)$

Let $$A(n)=\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{n+i}\frac{1}{2^{2i}} \qquad\qquad n\geq 1$$

We obtain

\begin{align*} A(n)&=\frac{1}{n}+\sum_{i=1}^{n-1}\binom{2i}{i}\frac{1}{n+i}\frac{1}{2^{2i}}\tag{8}\\ &=\frac{1}{n}+\sum_{i=0}^{n-2}\binom{2i+2}{i+1}\frac{1}{n+i+1}\frac{1}{2^{2i+2}}\tag{9}\\ &=\frac{1}{n}+\sum_{i=0}^{n-2}\binom{2i}{i}\frac{(2i+2)(2i+1)}{(i+1)^2}\frac{1}{n+i+1}\frac{1}{2^{2i+2}}\\ &=\frac{1}{n}+\sum_{i=0}^{n-2}\binom{2i}{i}\left(\frac{2n+1}{n+i+1}-\frac{1}{i+1}\right)\frac{1}{2^{2i+1}}\tag{10}\\ &=\frac{1}{n}+\frac{2n+1}{n}\sum_{i=0}^{n-2}\binom{2i}{i}\frac{1}{n+i+1}\frac{1}{2^{2i+1}} -\frac{1}{n}\sum_{i=0}^{n-2}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i+1}}\\ &=\frac{1}{n}+\frac{2n+1}{2n}\left(A(n+1)-\binom{2n-2}{n-1}\frac{1}{2n}\frac{1}{2^{2n-2}} -\binom{2n}{n}\frac{1}{2n+1}\frac{1}{2^{2n}}\right)\tag{11}\\ &\qquad-\frac{1}{n}\sum_{i=0}^{n-2}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i+1}}\\ &=\frac{2n+1}{2n}A(n+1)+\frac{1}{n}-\binom{2n-2}{n-1}\frac{2n+1}{n^2}\frac{1}{2^{2n}} -\binom{2n}{n}\frac{1}{n}\frac{1}{2^{2n+1}}\\ &\qquad-\frac{1}{n}\sum_{i=0}^{n-2}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i+1}}\\ &=\frac{2n+1}{2n}A(n+1)+\frac{1}{n}-\binom{2n-2}{n-1}\frac{2n-1}{n^2}\frac{1}{2^{2n}} -\binom{2n}{n}\frac{1}{n}\frac{1}{2^{2n+1}}\tag{12}\\ &\qquad-\frac{1}{n}\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i+1}}\\ &=\frac{2n+1}{2n}A(n+1)+\frac{1}{n}-\binom{2n}{n}\frac{1}{n}\frac{1}{2^{2n}} -\frac{1}{n}\sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i+1}}\tag{13}\\ \end{align*}

Comment:

• In (8) we separate the term with $i=0$

• In (9) we shift index $i\rightarrow i-1$

• In (10) we perform a partial fraction decomposition

• In (11) we replace the left sum with $A(n+1)$ and correct by subtracting the summands for $i=n-1$ and $i=n$

• In (12) we add term to the sum $i=n-1$ and update the term with $\binom{2n-2}{n-1}$ accordingly.

When analysing the recurrence relation (13) we focus on the first summand

$$\frac{2n+1}{2n}A(n+1)$$

of the RHS. Let's assume everything else is $0$ on the RHS of (13). Then we get following recurrence relation for $A(n)$

\begin{align*} A(1)&=1\\ A(n)&=\frac{2n-2}{2n-1}A(n-1)\qquad\qquad n\geq 1\\ \end{align*}

We obtain using double factorials \begin{align*} A(n)&=\frac{2n-2}{2n-1}A(n-1)\\ &=\frac{(2n-2)(2n-4)}{(2n-1)(2n-3)}A(n-2)\\ &=\ldots\\ &=\frac{(2n-2)(2n-4)\cdot\ldots\cdot2}{(2n-1)(2n-3)\cdot\ldots\cdot3}A(1)\\ &=\frac{(2n-2)!!}{(2n-1)!!}\\ &=\frac{(2n-2)!!(2n)!!}{(2n-1)!!(2n)!!}\\ &=\frac{2^{n-1}(n-1)!2^nn!}{(2n)!}\\ &=\frac{1}{n}2^{2n-1}\binom{2n}{n}^{-1}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

and the proof is finished provided we can show according to (13) the validity of

Step 3: A nice binomial identity regarding Catalan numbers

The following is valid \begin{align*} \sum_{i=0}^{n-1}\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}}=2\left(1-\frac{1}{2^{2n}}\binom{2n}{n}\right)\qquad\qquad n\geq 1\tag{14} \end{align*}

We show this identity (14) using the coefficient of operator $[z^n]$ to denote the coefficient $c_n$ of $z^n$ in a generating function $C(z)=\sum_{n=0}^{\infty}c_nz^n$.

We observe

\begin{align*} \sum_{i=0}^{n-1}&\binom{2i}{i}\frac{1}{i+1}\frac{1}{2^{2i}}\\ &=\sum_{i=0}^{n-1}[z^i]\frac{1-\sqrt{1-z}}{\frac{1}{2}z}\tag{15}\\ &=2[z^{i-1}]\frac{1-\sqrt{1-z}}{z}\frac{1}{1-z}\tag{16}\\ &=2[z^{i-1}]\left(\frac{1}{1-z}-\frac{1}{\sqrt{1-z}}+\frac{1-\sqrt{1-z}}{z}\right)\tag{17}\\ &=2\left(1-\binom{-\frac{1}{2}}{n-1}(-1)^{n-1}+\frac{1}{2n}\binom{2n-2}{n-1}\frac{1}{2^{2n-2}}\right)\tag{18}\\ &=2\left(1-\binom{2n-2}{n-1}\frac{1}{2n-2}+\frac{1}{2n}\binom{2n-2}{n-1}\frac{1}{2^{2n-2}}\right)\\ &=2\left(1-\frac{2n-1}{2n}\binom{2n-2}{n-1}\frac{1}{2^{2n-2}}\right)\\ &=2\left(1-\frac{1}{2^{2n}}\binom{2n}{n}\right)\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

and the last step is now successfully finished!

Comment:

• In (15) we use the generating function for the Catalan numbers in the form

$$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{n+1}\left(\frac{z}{4}\right)^n=\frac{1-\sqrt{1-z}}{\frac{1}{2}z}$$

• In (16) we observe that summing up the coefficients, i.e. $c_n \rightarrow \sum_{i=0}^{n}c_i$ corresponds to multiplication with $\frac{1}{1-z}$. It's just Cauchy multiplication of series

$$\frac{1}{1-z}\sum_{n=0}^{\infty}c_nz^n=\sum_{n=0}^{\infty}\left(\sum_{i=0}^{n}c_i\right)z^n$$

• In (17) we perform a partial fraction decomposition

• In (18) we use $\binom{-\frac{1}{2}}{n}=(-1)^n\binom{2n}{n}\frac{1}{2^{2n}}$

---

Note: I would appreciate to see a reference of the recurrence relation (7) of the Catalan Numbers \begin{align*} (n+1)\frac{C_n}{4^n}=1-\frac{1}{2}\sum_{i=0}^{n-1}\frac{C_i}{4^i}\qquad \qquad n\geq 0 \end{align*}

Maybe the kind reader could give a hint.