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!

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.
