Let $f(n)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}{n\choose k}{n-k\choose k}$. Show that $\sum_{n=0}^{\infty}f(n)x^n=\frac{1}{\sqrt{(1-3x)(1+x)}}$.
I managed to find the following recurrence relation for the trinomial coefficients in Wolfram: $(n+2)a_{n+2}=(2n+3)a_{n+1}+3(n+1)a_n$.
Now using $\sum_{n=0}^{\infty}(n+2)a_{n+2}x^n=\sum_{n=0}^{\infty}(2n+3)a_{n+1}x^n+\sum_{n=0}^{\infty}3(n+1)a_nx^n \implies \frac{dG}{G}=\frac{dx(x+3x^2)}{1-2x-3x^2}$ I can easily solve it except:
Question: How do I prove the relation $(n+2)a_{n+2}=(2n+3)a_{n+1}+3(n+1)a_n$?
Here is a direct computation of the generating function, using the binomial series: \begin{align*} \sum_{n=0}^\infty f(n)x^n\quad &=\sum_{n=0}^\infty x^n\sum_{0\leqslant 2k\leqslant n}\frac{n! }{k!^2(n-2k)!} =\sum_{k=0}^\infty\sum_{n=2k}^\infty\frac{n! \ x^n}{k!^2(n-2k)!} \\\color{gray}{[\text{replace $n$ with $n+2k$}]}\quad &=\sum_{k=0}^\infty\sum_{n=0}^\infty\frac{(n+2k)!}{k!^2 n!}x^{n+2k} =\sum_{k=0}^\infty\binom{2k}{k}x^{2k}\sum_{n=0}^\infty\binom{n+2k}{2k}x^n \\\color{gray}{[\text{use binomial series}]}\quad &=\sum_{k=0}^\infty\binom{2k}{k}x^{2k}(1-x)^{-2k-1} =\frac{1}{1-x}\sum_{k=0}^\infty\binom{2k}{k}\left(\frac{x}{1-x}\right)^{2k} \\\color{gray}{[\text{... and one more time}]}\quad &=\frac{1}{1-x}\left(1-\frac{4x^2}{(1-x)^2}\right)^{-1/2} =\quad\bbox[2pt,border:2pt solid]{\begin{matrix}\text{expected}\\\text{result}\end{matrix}} \end{align*} (the last step uses $\sum_{k=0}^\infty\binom{2k}{k}z^k=(1-4z)^{-1/2}$, another instance of the binomial series).
Another way is to use $\delta_{mn}$${}=\frac{1}{2\pi}\int_{-\pi}^\pi e^{i(m-n)t}\,dt$ and the multinomial theorem: $$f(n)=\frac{1}{2\pi}\sum_{\substack{n_1,n_2,n_3\geqslant 0\\n_1+n_2+n_3=n}}\frac{n!}{n_1!n_2!n_3!}\int_{-\pi}^\pi e^{i(n_2-n_3)t}\,dt=\frac{1}{2\pi}\int_{-\pi}^\pi(1+e^{it}+e^{-it})^n\,dt,$$ giving $\displaystyle\sum_{n=0}^\infty f(n)x^n=\frac1\pi\int_0^\pi\frac{dt}{1-x(1+2\cos t)}$ which is evaluated easily.