Simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$ I have to simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$. That because when $n$ and $m$ get large (eg. $n = 2^{64}$, $m = 2^{60}$), the computation complexity is too high. Could anybody help me simplify this?
 A: Consider that:
$$ \sum_{i=0}^{n}(-1)^i \binom{n}{i}x^i = (1-x)^n\tag{1} $$
and that
$$ \sum_{i=0}^{n}\binom{2n}{2i}x^i = \frac{(1+\sqrt{x})^n+(1-\sqrt{x})^n}{2}=P_m(x)\tag{2} $$
fulfils $P_m(x) = 2 P_{m-1}(x)-(1-x)P_{m-2}(x)$ (is a Lucas-type polynomial). The original sum is just the coefficient of $x^m$ in the product between the $RHS$s of $(1)$ and $(2)$, or:
$$ [x^{2m}] (1-x^2)^n\left(\frac{(1+x)^n+(1-x)^n}{2}\right)=[x^{2m}]\frac{(1+x)^{2n}(1-x)^n+(1-x)^{2n}(1+x)^m}{2}\tag{3} $$
that is:
$$ [x^{2m}]\frac{(1+x-x^2-x^3)^n+(1-x-x^2+x^3)^n}{2} = [x^{2m}] Q_n(x) \tag{4}$$
where $Q_n(x)$ is another Lucas-type polynomial that fulfils:
$$ Q_n(x) = 2(1-x^2) Q_{n-1}(x) - (1-x^2)^3 Q_{n-2}(x) \tag{5} $$
and $(4)$ gives that the wanted sum is a weigthed sum over the partitions of $2m$ in $n$ parts, in which every part is either $0,1,2$ or $3$.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Leftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Lets $\ds{\quad%
a_{m} \equiv \sum_{k = 0}^{m}\pars{-1}^{k}{n \choose k}{2n \choose 2m - 2k}}$
  for a fixed $\ds{n}$ value. I'll consider the function
  $\ds{\mathcal{F}\pars{z} \equiv \sum_{m = 0}^{\infty}a_{m}z^{m}}$ such that $\ds{a_{m} = \bracks{z^{m}}\mathcal{F}\pars{z}}$

\begin{align}
\mathcal{F}\pars{z} & = 
\sum_{m = 0}^{\infty}z^{m}
\sum_{k = 0}^{m}\pars{-1}^{k}{n \choose k}{2n \choose 2m - 2k} =
\sum_{k = 0}^{\infty}\pars{-1}^{k}{n \choose k}
\sum_{m = k}^{\infty}{2n \choose 2m - 2k}z^{m}
\\[3mm] & =
\sum_{k = 0}^{\infty}\pars{-1}^{k}{n \choose k}
\sum_{m = 0}^{\infty}{2n \choose 2m}z^{m + k}
\\[3mm] & =
\bracks{\sum_{k = 0}^{\infty}{n \choose k}\pars{-z}^{k}}
\bracks{\half\sum_{m = 0}^{\infty}{2n \choose m}z^{m/2} +
\half\sum_{m = 0}^{\infty}{2n \choose m}\pars{-z}^{m/2}}
\\[3mm] & =
\half\,\pars{1 -z}^{n}\bracks{\pars{1 + z^{1/2}}^{2n} + \pars{1 - z^{1/2}}^{2n}}
\\[3mm] &=
\half\braces{\bracks{\pars{1 -z}\pars{1 + 2z^{1/2} + z}}^{n} +
\bracks{\pars{1 -z}\pars{1 - 2z^{1/2} + z}}^{n}}
\\[3mm] & =
\half\sum_{\sigma = \pm}\pars{1 - 2\sigma z^{1/2} - 2\sigma z^{3/2} - z^{2}}^{n}
\\[3mm] & =
\half\sum_{\sigma = \pm}\sum_{a,b,c,d = 0}^{\infty}{n \choose a,b,c,d}
1^{a}\pars{2\sigma z^{1/2}}^{b}\pars{-2\sigma z^{3/2}}^{c}\pars{-z^{2}}^{d}
\\[3mm] & =
\half\sum_{\sigma = \pm}\sum_{a,b,c,d = 0}^{\infty}{n \choose a,b,c,d}
\pars{-1}^{c + d}\pars{2\sigma}^{b + c}z^{\pars{b + 3c}/2 + 2d}
\\[3mm] & =
\sum_{m = 0}^{\infty}z^{m}\bracks{\half\sum_{\sigma = \pm}\sum_{a,b,c,d = 0}^{\infty}{n \choose a,b,c,d}
\pars{-1}^{c + d}\pars{2\sigma}^{b + c}\delta_{b + 3c + 4d,2m}}
\\[3mm] & =
\sum_{m = 0}^{\infty}z^{m}\ \underbrace{\bracks{%
\sum_{a,c,d = 0}^{\infty}{n \choose a,2m - 3c - 4d,c,d}
\pars{-1}^{c + d}\,4^{m - c - 2d}}}_{\ds{\color{#f00}{a_{m}}}}
\end{align}
