How to deal with this double summation?

Question

I'm stuck with the proof of this result: $$2^n = \sum_{t=-\frac{n-1}{2}}^{\frac{n-1}{2}} \binom{n+1}{\frac{n+1}{2} + t} \sum_{k=\vert t \vert}^{\frac{n-1}{2}} \binom{\frac{n-1}{2}+k}{k} \binom{2k}{k+t} \frac{(-1)^t}{2^{2k}}$$ where $n$ is an odd integer.

How can we deal with this kind of summation? Thanks in advance.

Answer 1

Note: Finding a solution of OPs expression was an interesting experience because in intermediate steps we also obtain some other nice binomial identities. The following answer is divided into several steps. We start with a short

Overview:

In order to get a more convenient representation we transform OPs expression by setting $n\rightarrow 2n-1$ and so we have to show

The following is valid for $n\geq 1$:

\begin{align*} 2^{2n-1}=\sum_{t=-(n-1)}^{n-1}\binom{2n}{n+t} \sum_{k=|t|}^{n-1} \binom{n-1 + k}{k} \binom{2k}{k + t} \frac{(-1)^t}{2^{2k}}\tag{1} \end{align*}

Step 1: Elementary transformations

Let's denote the RHS of (1) with $A(n)$. We exchange sums, do some index shifting and obtain the following expression

\begin{align*} A(n)=\sum_{k=0}^{n-1}\binom{n-1+k}{k}\frac{1}{2^{2k}} \sum_{t=-k}^{k}\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t\qquad n\geq 1\tag{2} \end{align*}

Step 2: Egorychevs residual calculus of formal power series and Lagrange Inversion formula

This powerful technique is based upon Cauchys residue theorem and was introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

The most important part of this step is thereby applying the Lagrange Inversion Formula which is often helpful when everything else fails. I use the coefficient method as convenient notation.

We use this technique to simplify the inner sum of (2) and obtain for $n\geq 1$

\begin{align*} \sum_{t=-k}^{k}\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t =\frac{\binom{2k}{k}\binom{2n}{n}}{\binom{n+k}{k}}\qquad 0\leq k \leq n-1\tag{3} \end{align*}

Now putting (3) in (2) we get

\begin{align*} A(n)=n\binom{2n}{n}\sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{n+k}\frac{1}{2^{2k}}\qquad\qquad n \geq 1\tag{4} \end{align*}

Note: Next we meet two nice binomial identities. Since we want to show that $A(n)=2^{2n-1}$, we have to prove according to (4) in

Step 3: A nice binomial identity

We show the following is valid:

\begin{align*} \sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{n+k}\frac{1}{2^{2k}}=2^{2n-1}\frac{1}{n}\binom{2n}{n}^{-1}\qquad\qquad n \geq 1\tag{5} \end{align*}

In order to solve (5) we will simplify the LHS. By doing so we obtain another identity which is to prove in an intermediate

Step 4: Another binomial identity regarding Catalan numbers

\begin{align*} \sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{k+1}\frac{1}{2^{2k}}=2-\frac{1}{2^{2n-1}}\binom{2n}{n}\qquad\qquad n \geq 1\tag{6} \end{align*}

Note: Identity (6) is interesting. Writing $C_n=\frac{1}{n+1}\binom{2n}{n}$ 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_{k=0}^{n-1}\frac{C_k}{4^k}\qquad \qquad n\geq 0\tag{7} \end{align*} The recurrence relation (7) 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 (6) 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{8} \end{align*} of the Catalan numbers evaluated at $z=\frac{1}{4}$. The series is uniformly converging in the open disc $|z|<\frac{1}{4}$ and it also converges at $z=\frac{1}{4}$.

We obtain using the RHS of (6) and the generating function from (8): \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:

Step 1: Elementary transformations

Let's denote the RHS of OPs expression with $A(n)$.

We observe according to (1)

\begin{align*} A(n)&=\sum_{t=-(n-1)}^{n-1}\binom{2n}{n+t} \sum_{k=|t|}^{n-1}\binom{n-1+k}{k}\binom{2k}{k+t}\frac{(-1)^t}{2^{2k}}\\ &=\sum_{t=-(n-1)}^{-1}\binom{2n}{n+t} \sum_{k=-t}^{n-1}\binom{n-1+k}{k}\binom{2k}{k+t}\frac{(-1)^t}{2^{2k}}\\ &\qquad\qquad+\binom{2n}{n}\sum_{k=0}^{n-1}\binom{n-1+k}{k}\binom{2k}{k}\frac{1}{2^{2k}}\tag{9}\\ &\qquad+\sum_{t=1}^{n-1}\binom{2n}{n+t} \sum_{k=t}^{n-1}\binom{n-1+k}{k}\binom{2k}{k+t}\frac{(-1)^t}{2^{2k}}\\ &=\sum_{t=1}^{n-1}\binom{2n}{n+t} \sum_{k=t}^{n-1}\binom{n-1+k}{k}\binom{2k}{k+t}\frac{(-1)^t}{2^{2k}}\\ &\qquad\qquad+\binom{2n}{n}\sum_{k=0}^{n-1}\binom{n-1+k}{k}\binom{2k}{k}\frac{1}{2^{2k}}\tag{10}\\ &\qquad+\sum_{t=1}^{n-1}\binom{2n}{n+t} \sum_{k=t}^{n-1}\binom{n-1+k}{k}\binom{2k}{k+t}\frac{(-1)^t}{2^{2k}}\\ &=\sum_{k=1}^{n-1}\binom{n-1+k}{k}\frac{1}{2^{2k}}\sum_{t=1}^{k}\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t\\ &\qquad+\sum_{k=0}^{n-1}\binom{n-1+k}{k}\frac{1}{2^{2k}}\binom{2n}{n}\binom{2k}{k}\tag{11}\\ &\qquad+\sum_{k=1}^{n-1}\binom{n-1+k}{k}\frac{1}{2^{2k}}\sum_{t=1}^{k}\binom{2n}{n+t}\binom{2k}{k-t}(-1)^t\\ &=\sum_{k=1}^{n-1}\binom{n-1+k}{k}\frac{1}{2^{2k}}\sum_{t=-k}^{k}\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t\tag{12}\\ \end{align*}

and (2) follows.

Comment:

• In (9) we split the sum according to the sign of $t$

• In (10) we exchange in the first sum $t$ with $-t$. Observe that $\binom{2n}{n+t}=\binom{2n}{n-t}$

• In (11) we exchange the inner and outer sums

• In (12) we collect the three sums; now inner and outer sums exchanged

Step 2: Applying Egorychevs residual calculus of formal power series and Lagrange Inversion formula

We now focus on the inner sum of (13). We thereby use 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_{t=-k}^{k}&\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t\\ &=\sum_{t=-k}^{k}\binom{2k}{k-t}[z^{n-t}](1+z)^{2n}(-1)^t\\ &=[z^n](1+z)^{2n}\sum_{t=-k}^{k}\binom{2k}{k-t}(-z)^t\\ &=(-1)^k[z^{n+k}](1+z)^{2n}\sum_{t=-k}^{k}\binom{2k}{k-t}(-z)^{t+k}\\ &=(-1)^k[z^{n+k}](1+z)^{2n}\sum_{t=0}^{2k}\binom{2k}{t}(-z)^{t+k}\\ &=(-1)^k[z^n](1+z)^{2n}\frac{(1-z)^{2k}}{z^k}\tag{13} \end{align*}

Now we apply the Lagrange Inversion Formula (LIF). We use the notation according to Lagrange Inversion: when and how by R. Sprugnoli etal.

We take a look at (13) and see following shape \begin{align*} (-1)^k[z^n](1+z)^{2n}\frac{(1-z)^{2k}}{z^k}=(-1)^k[z^n]F(z)\Phi^n(z)\tag{14} \end{align*}

with $$F(z)=\frac{(1-z)^{2k}}{z^k}\qquad\text{and}\qquad\Phi(z)=(1+z)^2$$

Applying LIF to (14) the corresponding generating function $\mathcal{G}([z^n]F(z)\Phi^n(z))$ is

\begin{align*} \mathcal{G}\left([z^n]F(z)\Phi^n(z)\right)=\left.\frac{F(w)}{1-z\Phi^{\prime}(w)}\right|_{w=z\Phi(w)} \end{align*}

Since \begin{align*} w=z\Phi(w)=z(1+w)^2\tag{15} \end{align*} we obtain \begin{align*} \frac{F(w)}{1-z\Phi^{\prime}(w)}&=\frac{(1-w)^{2k}}{w^k}\frac{1}{1-2z(1+w)}\\ &=\frac{(1-w)^{2k}}{w^k}\frac{1}{1-2\frac{w}{1+w}}\\ &=\frac{(1-w)^{2k}}{w^k}\frac{1+w}{1-w}\tag{16}\\ \end{align*} From (15) we get the quadratic equation in $w$ $$zw^2-(1-2z)w+z=0$$ with the solution $$w_{1,2}=\frac{1\pm\sqrt{1-4z}}{2z}-1$$ We have to take the solution $w=\frac{1-\sqrt{1-4z}}{2z}-1$ in order to obtain a generating function.

Using this solution we get \begin{align*} \frac{(1-w)^2}{w}=\frac{1-4z}{z}\qquad\text{and}\qquad\frac{1+w}{1-w}=\frac{1}{\sqrt{1-4z}} \end{align*} Now putting this into (16) we get \begin{align*} \frac{F(w)}{1-z\Phi^{\prime}(w)}&=\frac{(1-w)^{2k}}{w^k}\frac{1+w}{1-w}\\ &=\left(\frac{1-4z}{z}\right)^k\frac{1}{\sqrt{1-4z}}\tag{17} \end{align*} We conclude combining (14) and (17) \begin{align*} (-1)^k[z^n]&(1+z)^{2n}\frac{(1-z)^{2k}}{z^k}\\ &=(-1)^k[z^n]\left(\frac{1-4z}{z}\right)^k\frac{1}{\sqrt{1-4z}}\\ &=(-1)^k[z^{n+k}](1-4z)^{k-\frac{1}{2}}\\ &=(-1)^k\binom{k-\frac{1}{2}}{n+k}(-4)^{n+k}\\ &=(-1)^n\binom{k-\frac{1}{2}}{n+k}4^{n}\tag{18} \end{align*}

A small calculation of (18) using double factorials gives \begin{align*} \binom{k-\frac{1}{2}}{n+k}&= \frac{\left(k-\frac{1}{2}\right)\left(k-\frac{3}{2}\right)\cdot\ldots\cdot\left(k-\frac{1}{2}-(n+k-1)\right)}{(n+k)!}\\ &=\frac{1}{2^{n+k}}\frac{(2k-1)(2k-3)\cdot\ldots\cdot(1-2n)}{(n+k)!}\\ &=\frac{1}{2^{n+k}}\frac{(2k-1)!!(2n-1)!!(-1)^n}{(n+k)!}\\ &=\frac{1}{2^{n+k}}\frac{(2k)!}{(2k)!!}\frac{(2n)!}{(2n)!!}(-1)^n\frac{1}{(n+k)!}\\ &=\frac{1}{4^{n+k}}\frac{(2k)!}{k!}\frac{(2n)!}{n!}(-1)^n\frac{1}{(n+k)!}\\ &=\frac{1}{4^{n+k}}\binom{2k}{k}\binom{2n}{n}\binom{n+k}{k}^{-1}(-1)^n \end{align*} Combining this result with (13) and (18) we get

\begin{align*} \sum_{t=-k}^{k}&\binom{2n}{n-t}\binom{2k}{k-t}(-1)^t=\frac{1}{2^{2k}}\binom{2k}{k}\binom{2n}{n}\binom{n+k}{k}^{-1}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*} and the claim (4) follows.

So we have the situation (4)

\begin{align*} A(n)=n\binom{2n}{n}\sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{n+k}\frac{1}{2^{2k}}\qquad\qquad n \geq 1 \end{align*} and since we want to show that $A(n)=2^{2n-1}$ we have to prove in the following two steps

Step 3 and Step 4:

\begin{align*} \sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{n+k}\frac{1}{2^{2k}}=2^{2n-1}\frac{1}{n}\binom{2n}{n}^{-1}\qquad n\geq 1 \end{align*}

and in an intermediate step we also have to show the following binomial identity involving the ubiquituos Catalan numbers

\begin{align*} \sum_{k=0}^{n-1}\binom{2k}{k}\frac{1}{k+1}\frac{1}{2^{2k}}=2-\frac{1}{2^{2n-1}}\binom{2n}{n}\qquad\qquad n \geq 1 \end{align*}

Note: The validity of these two identities is already shown as part 2 and part 3 of my answer to a Hard binomial sum

and so the proof is finished.

---

Note: I'm interested if somebody could provide a reference to 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*}

In fact I would like to know if this relation is already known. Thanks a lot in advance.