Generating function for $a_n = \sum_{k=0}^{n-2} a_ka_{n-k-2}$ Let $a_n$ be a sequence following the recurrence relation $$a_n = \sum_{k=0}^{n-2} a_ka_{n-k-2}$$ with initial conditions $a_0 = a_1 = 1$.
We have to find the generating function for $a_n$ that does not contain an infinite series.

Let $f(x) = \sum_{k=0}^{n} a_k$. We know that $$\sum_{k=0}^{n-2} a_ka_{n-k-2}x^{n-2} = \left(\sum a_k x^k \right)  \left(\sum a_{n-k-2} x^{n-k-2}\right)$$
After that, I am not able to proceed.
Can someone help?

Note that $a_2 = 1$ and $a_3 = 2$. Thus simplifying from the answer below:
$$x^2f^2(x) -f(x) + (1+x) = 0.$$
And solving for the quadratic function we have $$f(x) = \frac{1-\sqrt{1-4x^2(x+1)}}{2x^2}$$
 A: Naturally, you would consider the square of the generating function:
$$f^2(x) = \sum_{i=0}^\infty a_ix^i \sum_{j=0}^\infty a_jx^j = \sum_{n=0}^\infty \sum_{k=0}^na_ka_{n-k}x^n = a_0^2 + 2a_0a_1x + \sum_{n=2}^\infty a_{n+2}x^n =$$
$$= 1+2x + x^{-2} \sum_{n=2}^\infty a_{n+2}x^{n+2} = 1+2x+x^{-2}(f(x) - a_0-a_1x-a_2x^2-a_3x^3).$$
You can finish now?
A: The expansion of $\sqrt{1+x}$ is $$\sum_{k=0}^{\infty}\binom{1/2}{k}x^k = 1 + \sum_{k=1}^\infty\frac{(1/2)(1/2 - 1) \cdots (1/2 - k + 1)}{k!}x^k = 1 + \frac{1}{2}x - \frac{1}{8}x^2 + \frac{1}{16}x^3 - \frac{5}{128}x^4 + \cdots.$$ Then the expansion of $\sqrt{1 - 4x^2(x + 1)}$ is \begin{align*}1 + \frac{1}{2}(-4x^2(x+1)) - \frac{1}{8}(-4x^2(x+1))^2 + \frac{1}{16}(-4x^2(x+1))^3 - \frac{5}{128}(-4x^2(x+1))^4 + \cdots\end{align*} so $1 - \sqrt{1 - 4x^2(x + 1)}$ is \begin{align*}- \frac{1}{2}(-4x^2(x+1)) + \frac{1}{8}(-4x^2(x+1))^2 - \frac{1}{16}(-4x^2(x+1))^3 + \frac{5}{128}(-4x^2(x+1))^4 + \cdots\end{align*} and $\frac{1 - \sqrt{1 - 4x^2(x + 1)}}{2x^2}$ is \begin{align*}- \frac{1}{4x^2}(-4x^2(x+1)) + \frac{1}{16x^2}(-4x^2(x+1))^2 - \frac{1}{32x^2}(-4x^2(x+1))^3 + \frac{5}{256x^2}(-4x^2(x+1))^4 + \cdots\end{align*} which simplifies to $$1 + x + x^2(x+1)^2 + 2x^4(x+1)^3 + 5x^6(x+1)^4 +\cdots = 1 + x + x^2 + 2x^3 + 3x^4 + \cdots$$ and the coefficients are the terms you are looking for.
