<s>[INST] Let $f(n)=\sum_{k=0}^{\left\lfloor n/2\right\rfloor} {2k \choose k}{n \choose 2k}$ . Show that $\sum_{n\geq 0}^{} f(n)x^n=\frac{1}{\sqrt{1-2x-3x^2}}$ Using the multinomial theorem, one can show that $f(n)$ is the coefficient of $x^n$ of the polynomial $(1+x+x^2)^n$. There are $3$ obvious ways to show the equation in the title:

*

*First, you can square the $2$ sides of the equation and then multiply with $1-2x-3x^2$. In that case, the coefficients of the left formal power series seems too much.


*Second, we can factorize the polynomial,
$$
   1-2x-3x^2=(-3)(x+1)(x-1/3)=(1+x)(1-3x)
   $$
$$\mbox{and use the formula ,}\quad
   \sqrt{1+F(x)}=\sum_{n\geq 0}^{}(-1)^n \frac{1}{4^n}{2n \choose
   n}F(x)^n
   $$
for $F(x)=x , G(x)=-3x$, then multiply the formal power
series and see if the equation holds.


*The third way is to use the
previous method for $F(x)=-(2x+3x^2)$. In the 2 last methods the
numbers arent very far from those we want, but i cant prove it. I
think that i am missing some identity with binomial coefficients and
thats why i cant solve it.
 [/INST] Here's a way that doesn't require knowing the result ahead of time.
\begin{align}
\sum_{n \ge 0} f(n) x^n 
&= \sum_{n \ge 0}\sum_{k=0}^{\left\lfloor n/2\right\rfloor} \binom{2k}{k}\binom{n}{2k} x^n \\
&= \sum_{k \ge 0}\binom{2k}{k} \sum_{n\ge 2k} \binom{n}{2k} x^n \\
&= \sum_{k \ge 0}\binom{2k}{k} \frac{x^{2k}}{(1-x)^{2k+1}} \\
&= \frac{1}{1-x}\sum_{k \ge 0}\binom{2k}{k} \left(\left(\frac{x}{1-x}\right)^2\right)^k \\
&= \frac{1}{1-x}\cdot\frac{1}{\sqrt{1-4\left(\frac{x}{1-x}\right)^2}} \\
&= \frac{1}{\sqrt{(1-x)^2-4x^2}} \\
&= \frac{1}{\sqrt{1-2x-3x^2}}
\end{align}
</s>