Simplifying a summation with binomial coefficients 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!
 A: 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.
A: 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:

*

*Number of paths ending at $(n,k)$ (denoted by $N(n,k)$): $[(n+k)\text{ is even}]\binom{n}{(n+k)/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)$


*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)$


*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.
A: 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 ...
