# How to deal with this double summation?

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.

• This might help: Try the substitution $n = 2m + 1$ and prove the identity there. (It will get rid of all your fractions.) – Sammy Black Feb 9 '15 at 6:20
• Another possibly-useful thing to do is shift the $t$ summation to start at zero (i.e. substitute $s=t+(n-1)/2$). That cleans a few things up. – Semiclassical Feb 9 '15 at 6:24
• @SammyBlack: Thanks for your comments, but the fractions aren't the troubles for me :-) for the same reason that you point out with the substitution. – rafaeldf Feb 9 '15 at 6:27
• @Semiclassical: I just wrote in a compact form the outer summation. The shift that you suggest isn't the only way to do that the outer summation start at zero, also you can notice that the inner summation is symmetric respect to zero, so the negative terms $t$ can be "simplified". This compact way to write the double summation is related with a big problem that I'm trying to solve, so this question (as particular case) try to do a brainstorm or bring an insight ;-) – rafaeldf Feb 9 '15 at 6:34
• @rafaeldf: well, given that you've started with something larger, it may be helpful to give a bit of the manuevering that got you here so that we don't walk your steps backwards. – Semiclassical Feb 9 '15 at 6:37

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

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:

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

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)

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

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:

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

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.

• @Semiclassical: According to your comments to OPs question my answer might be of interest to you. Regards, – Markus Scheuer Mar 22 '15 at 8:26
• This method could be useful for me, thanks for your helpful and clear answer. I have a lot of "nice binomial identities" where this come from! ;-) – rafaeldf May 10 '15 at 1:43
• @rafaeldf: You're welcome! ... and I like nice binomial identities! :-) – Markus Scheuer May 10 '15 at 6:10
• It's easy to believe that you like it so much ;-) Thanks again to put me on notice about this powerful tool that has proved to be useful for me by my own hands! ;-) – rafaeldf May 10 '15 at 9:08