Simplifying a summation with binomial coefficients

Question

Simplify the sum

$$ f(k,q)=\sum_{i=0}^k\binom{2i}{i+q}\binom{2k-2i}{k-i} $$

where $k,q$ are given integers satisfying $0<q\le k$.

I tried to simplify it combinatorially. For a lattice path $p$ using steps (1,1) and (1,-1) and starts from the origin, define $g_q(p)$ to be the number of intersections between $p$ and the line $y=2q$. One can notice that $f(k,q)$ calculates the sum $g_q(p)$ for all lattice paths from the origin to (2k,2q). If we enumerate the rightmost intersection between the path and the line $y=2q$, and denote its $x$ position by $2t$, then we have

$$ f(k,q)=\sum_{t=0}^k\left(\binom{2t}{t+q}-2\binom{2t-1}{t+q}\right)4^{k-t} $$

However this does not make the problem easier. How should I proceed? Any help is appreciated!

Answer 1

Supposing we seek to simplify

$$\sum_{j=0}^k {2j\choose j+q} {2k-2j\choose k-j}.$$

where $0\le q\le k.$ This is

$$[z^k] (1+z)^{2k} \sum_{j=0}^k {2j\choose j+q} \frac{z^j}{(1+z)^{2j}}.$$

Here the coefficient extractor enforces the upper limit of the sum and we find

$$[z^k] (1+z)^{2k} \sum_{j\ge 0} {2j\choose j+q} \frac{z^j}{(1+z)^{2j}}.$$

At this point we see that we will require residues and complex integration and continue with

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k}}{z^{k+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{q+1}} \sum_{j\ge 0} \frac{(1+w)^{2j}}{w^j} \frac{z^j}{(1+z)^{2j}} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k}}{z^{k+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{q+1}} \frac{1}{1-z(1+w)^2/w/(1+z)^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+2}}{z^{k+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{q}} \frac{1}{w(1+z)^2-z(1+w)^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+2}}{z^{k+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{q}} \frac{1}{(w-z)(1-wz)} \; dw \; dz.$$

For the geometric series to converge we must have $|z(1+w)^2/w/(1+z)^2| \lt 1$ or $|z/(1+z)^2| \lt |w/(1+w)^2|.$ This requires $\varepsilon/(1-\varepsilon)^2 \lt \gamma/(1+\gamma)^2.$ We will also require $w=z$ to be inside the contour for $w$ so we need $\varepsilon \lt \gamma.$ With $\varepsilon \ll 1$ and $\gamma \ll 1$ we may take $\varepsilon = \gamma^2$ for the latter inquality. We then get for the inquality from the geometric series $\gamma^2/(1-\gamma^2)^2 \lt \gamma / (1+\gamma)^2$ or $\gamma \lt (1-\gamma^2)^2/(1+\gamma)^2$ or $\gamma \lt (1-\gamma)^2.$ This holds for $\gamma\lt 1-1/\varphi$ with $\varphi$ the golden mean.

Now we have the pole at zero and the one at $w=z$ inside the contour in $w$. This means we can evaluate the integral by using the fact that residues sum to zero, taking minus the residue at $w=1/z$ and minus the residue at infinity, which is zero by inspection, however. (The pole at $w=1/z$ has modulus $1/\varepsilon$ and is outside the contour.) Computing minus the residue at $w=1/z$ we write

$$- \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+2}}{z^{k+2}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{q}} \frac{1}{(w-z)(w-1/z)} \; dw \; dz.$$

With the sign change we obtain

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+2}}{z^{k+2}} z^q \frac{1}{1/z-z} \; dz = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+2}}{z^{k-q+1}} \frac{1}{1-z^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{2k+1}}{z^{k-q+1}} \frac{1}{1-z} \; dz.$$

This is zero when $q\gt k$ and otherwise

$$\sum_{j=0}^{k-q} {2k+1\choose j} = \sum_{j=0}^k {2k+1\choose j} - \sum_{j=k-q+1}^k {2k+1\choose j}$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ 4^k - \sum_{j=k-q+1}^k {2k+1\choose j}}$$

which is a closed form term plus a sum of $q$ terms. E.g. with $q=0$ we obtain $4^k$ and with $q=1,$ $4^k - {2k+1\choose k}$. For $q=2$ we have $4^k - {2k+1\choose k-1} - {2k+1\choose k}$ and so on.

Answer 2

hint

Since $q$ and $i$ are non negative, the first binomial is null unless $q+i \le 2i$, i.e. $q \le i$, i.e. the sum actually starts from $q$.
Then change the index from $i$ to $j=k-i$.
At this stage express the binomials through the gamma function, and apply the duplication formula for gamma ...

Answer 3

Finally I got a combinatorial method for this problem. Below "path" means lattice path using steps $(1,1)$ and $(1,-1)$ and starting from the origin $(0,0)$. And I'll list some well-known formulas that might be used in the proof:

1. Number of paths ending at $(n,k)$ (denoted by $N(n,k)$): $[(n+k)\text{ is even}]\binom{n}{(n+k)/2}$

2. Number of paths ending at $(n,q)$ and touch the line $y=r$ at least once ($q<r$) (Hint: Reflection Principle): $N(n,2r-q)$

3. Number of paths consisting of $n$ steps and touch the line $y=r$ at least once (Hint: sum up formula 2): $N(n, r)+2\sum_{i=r+1}^nN(n,i)$

4. Number of paths consisting of $n$ steps and never go below the $x$ axis ($y=0$) (Hint: sum up formula 3): $\binom{n}{\lfloor n/2\rfloor}$

Let's consider the combinatorial meaning of the summation. One can notice that $f(k,q)$ counts all the paths consisting of $2k+1$ steps whose final $y$ coordinate is $2q+1$ or more: we enumerate the rightmost intersection between the path and the line $y=2q$, and denote its $x$ coordinate by $2t$ (clearly it must be even). So the left part has $N(2t,2q)=\binom{2t}{t+q}$ possibilities, and the right part, since it cannot go below $y=2q+1$ except for the first step ($(2t,2q)$ is already the rightmost intersection), we'll have $\binom{2k+1-2i-1}{(2k+1-2i-1)/2}=\binom{2k-2i}{k-i}$ possibilities (formula 4).

And according to formula 1, we have another form for the quantity, that is to say

$$ \begin{aligned} f(k,q)&=\sum_{i=2q+1}^{2k+1}N(2k+1,i)\\ &=\sum_{i=q}^k\binom{2k+1}{k+i+1}=\sum_{i=0}^{k-q}\binom{2k+1}i \end{aligned} $$

This yields the same result as Marko Riedel's answer. Sorry for my verbose description and poor English, I tried my best to make it clear for everyone. Feel free to comment if you think I have typo and mistake.