Find closed form solution using generation function for the binomial coefficients

Question

I don't have any idea how to start this problem. Could you give a hint?

Find closed form solution using generation function for the binomial coefficients:

$$a_n:=\sum_{k=0}^{n}\binom{n}{k}^2(-1)^k$$

Answer 1

Note that: $a_n=\sum_{k \geq 0} \binom{n}{k}^2(-1)^k=\sum_{k \geq 0} \binom{n}{k} (-1)^k \times\binom{n}{n-k} $, since $\binom{n}{n-k}=\binom{n}{k}$, this is readily a convolution (of the coefficients of $(1-x)^n$ and the coefficients of $(1+x)^n$).

Looking closely, this is $$a_n=[x^n]\left\{(1-x)^n (1+x)^n\right\} = [x^n]\left\{(1-x^2)^n\right\}$$

Thus it follows that if $n$ is odd, then $a_n = 0$, because $(1-x^2)^n$ has only even powers of $x$. And, if $n$ is even, then $a_n = \binom{n}{n/2} (-1)^{n/2}$ by the Binomial Theorem.

Notation: $[x^n]\left\{p(x)\right\}$ denotes the coefficient of $x^n$ in $p(x)$.

Answer 2

This is one of these hypergeometric sums where it is not easy to make progress without using Sister Celine's method / Zeilberger's algorithm, which is not difficult to implement, at least in its basic form.

This algorithm produces the following recurrence for your sum: $$n a_n+4(n-1) a_{n-2} = 0.$$ Note that we have $a_0=1$ and $a_1=0.$

Re-write the recurrence so that it becomes apparent that it produces a product: $$a_n = -4\frac{n-1}{n} a_{n-2}.$$

This implies that for $n$ odd, we have $a_n = 0,$ and for $n$ even, we have $$a_n = (-4)^{n/2} \prod_{k=1}^{n/2} \frac{2k-1}{2k} = (-4)^{n/2} \prod_{k=1}^{n/2} \frac{(2k-1)2k}{(2k)^2} = (-4)^{n/2} n! \frac{1}{4^{n/2}} \prod_{k=1}^{n/2} \frac{1}{k^2}\\ = (-1)^{n/2} \frac{n!}{(n/2)!^2} = (-1)^{n/2} {n\choose n/2}.$$

Now the generating function of the central binomial coefficients is well known and given by $$\frac{1}{\sqrt{1-4z}} =\sum_{n\ge 0} {2n\choose n} z^n.$$ To match up the coefficient $z^n$ with ${n\choose n/2}$ we evidently have to replace $z$ by $z^2$ in this generating function (which also has the nice effect of producing zero values for odd indices of $a_n$ as required), getting $$\frac{1}{\sqrt{1-4z^2}} =\sum_{n\ge 0} {2n\choose n} z^{2n}.$$ Finally add in the sign, noting that $i^{2n} = (-1)^n,$ where $i$ is the imaginary unit, for the end result $$\frac{1}{\sqrt{1-4(iz)^2}} = \frac{1}{\sqrt{1+4z^2}}.$$ Addendum. In order to verify the recurrence put $$F_{n,j} = (-1)^j {n\choose j}^2$$ and check that $$F_{n,j}\frac{n}{n-1} - (F_{n-1,j}-F_{n-1,j-1}) \frac{2n-1}{n-1} + (F_{n-2, j} +2 F_{n-2,j-1} + F_{n-2,j-2}) = 0.$$ This equation is the output from Sister Celine. Now adding over $j$ this becomes $$a_n\frac{n}{n-1} - (a_{n-1}-a_{n-1}) \frac{2n-1}{n-1} + (a_{n-2} +2 a_{n-2} + a_{n-2}) = 0$$ which is $$a_n\frac{n}{n-1} + 4 a_{n-2} =0,$$ precisely the recurrence we are trying to verify.

Answer 3

$\newcommand{\+}{^{\dagger}}% \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}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ $\ds{% a_{n} \equiv \sum_{k = 0}^{n}{n \choose k}^{2}\pars{-1}^{k}: {\large ?}}$

\begin{align} a_{n} &= \sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k} \sum_{\ell = 0}^{n}{n \choose \ell}\delta_{\ell, k} = \sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k} \sum_{\ell = 0}^{n}{n \choose \ell}\oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {1 \over z^{\ell - k + 1}} \\[3mm]&= \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z} \sum_{k = 0}^{n}{n \choose k}\pars{-z}^{k} \sum_{\ell = 0}^{n}{n \choose \ell}\pars{1 \over z}^{\ell} = \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z}\,\pars{1 - z}^{n} \pars{1 + {1 \over z}}^{n} \\[3mm]&= \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n + 1}}\,\pars{1 - z^{2}}^{n} = \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n + 1}} \sum_{\ell = 0}^{n}{n \choose \ell}\pars{-z^{2}}^{\ell} \\[3mm]&= \sum_{\ell = 0}^{n}{n \choose \ell}\pars{-1}^{\ell} \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n - 2\ell + 1}} = \left\lbrace% \begin{array}{ccl} 0 & \quad\mbox{if} & n\,\,\,\mbox{is}\,\,\,{\it odd} \\[2mm] \pars{-1}^{n/2}{n \choose {n \over 2}} & \quad\mbox{if} & n\,\,\,\mbox{is}\,\,\,{\it even} \end{array}\right. \end{align}

$$\color{#0000ff}{\large% \sum_{k = 0}^{n}{n \choose k}^{2}\pars{-1}^{k} = \left\lbrace% \begin{array}{ccl} 0 & \quad\mbox{if} & n\,\,\,\mbox{is}\,\,\,{\it odd} \\[2mm] \pars{-1}^{n/2}{n \choose {n \over 2}} & \quad\mbox{if} & n\,\,\,\mbox{is}\,\,\,{\it even} \end{array}\right.} $$

Answer 4

Let define $$a_n=\sum_{k=0}^n(-1)^k\binom{n}{k}^2=\sum_{k=0}^n t_k.$$ Observing the ratio $$ \frac{t_{k+1}}{t_k}=\frac{(-1)^{k+1}\binom{n}{k+1}^2}{(-1)^k\binom{n}{k}^2}=-\frac{(k-n)^2}{(k+1)^2}=\frac{(k-n)(k-n)}{(k+1)(k+1)}(-1) $$ we see that $a_n$ can be expressed with the hypergeometric function $_2F_1$ as $$ a_n=\;_2F_1\left(\matrix{-n,\;-n\\1}\Bigg|-1\right). $$

Using the Kummer's identity for $b-a+c=1$ and $b$ negative integer $$ _2F_1\left(\matrix{a,\;b\\c}\Bigg|-1\right)=2\cos\left(\tfrac{\pi b}{2}\right) \frac{\Gamma(|b|)\Gamma(b-a+1)}{\Gamma\left(\frac{|b|}{2}\right)\Gamma\left(\frac{b}{2}-a+1\right)} $$ one has $$ a_n =2\cos\left(\tfrac{\pi n}{2}\right) \frac{\Gamma(n)}{\Gamma\left(\tfrac{n}{2}\right)\Gamma\left(\frac{n}{2}+1\right)} $$ and observing that $$ \frac{\Gamma(n)}{\Gamma\left(\tfrac{n}{2}\right)\Gamma\left(\frac{n}{2}+1\right)} =\frac{(n-1)!}{(n/2-1)!(n/2)!}=\frac{n/2}{n}\frac{n!}{(n/2)!(n/2)!} =\frac{1}{2}\binom{n}{n/2} $$ we obtain finally

$$ a_n=\frac{(-1)^{n/2}\left[1+(-1)^n\right]}{2}\binom{n}{n/2} $$