<s>[INST] Need Help with Mistake in Generating Function for Nonlinear Recurrence relation I'm having a bit of trouble finding the generating function for the following recurrence relation:
$$
w_n -1 = \sum _{k=1}^{n-1} w_k w_{n-k}, \quad n \geq 2, \; w_0 = 0, \; w_1 = 1.
$$
I set out to find a generating function $F$ such that
$$
F(x) = \sum _{n=0}^{\infty} w_n x^n.
$$
First, I multiplied the LHS of the equation with $x^n$ and summed, obtaining
$$
F(x) - (w_0 + w_1 x) - \sum _{n=0}^{\infty} x^n = F(x)-x-\frac{1}{1-x}.
$$
For the RHS, we can observe that the $n$-th coefficient of $F(x)^2$ concide with
$$
\sum _{k=1}^{n-1} w_k w_{n-k}.
$$
That is, if we perform the product term by term and collect, we can check
$$
F(x)^2 = w_1 w_1 x^2 + (w_1 w_2 + w_2 w_1)x^3 + (w_1 w_3 + w_2 w_2 + w_3 w_1)x^4 + \cdots
$$
and this is possible because $w_0 = 0$. Equating both expressions, I get
$$
F(x) - x - \frac{1}{1-x} = F(x)^2.
$$
But this equation is wrong! Because if I take $x=0$, 
$$
(0) - (0) - \frac{1}{1 - (0)} = 0 \implies -1 = 0.
$$
I haven't been able to spot my mistake. Any and all help is appreciated :)
 [/INST] Multiplying both sides of the recurrence by $x^n$ and summing for $n=2$ to infinity:
$$
\sum_{n=2}^\infty w_nx^n = \sum_{n=2}^\infty \sum_{k=1}^{n-1} w_kw_{n-k}x^n + \sum_{n=2}^\infty x^n.
$$
Because $w_0=0$, $w_1=1$, and $w_n$ is a sum of products of $w_1,\ldots,w_{n-1}$ plus one, $w_n$ is nonnegative for all $n$. So by Tonelli's theorem we may interchange the order of summation:
$$
F(x) - x = \sum_{k=1}^\infty  w_k\sum_{n=k+1}^\infty w_{n-k}x^n + \frac{x^2}{1-x}.
$$
Shifting the index of the sum over $k$ down by $n$, we have
$$
F(x) = \sum_{k=1}^\infty w_k x^k\sum_{n=1}^\infty w_nx^n + x + \frac{x^2}{1-x}.
$$
But since $w_0=0$, $\sum_{n=0}^\infty w_nx^n = \sum_{k=1}^\infty w_kx^k = F(x)$, so we have
$$
F(x) = F(x)^2 + x + \frac{x^2}{1-x},
$$
and hence
$$
F(x) - F(x)^2 = x + \frac{x^2}{1-x}.
$$
The roots of this equation are
$$
F(x) = \frac{1}{2} \left(1-\frac{\sqrt{5 x-1}}{\sqrt{x-1}}\right),\quad F(x) = \frac{1}{2} \left(\frac{\sqrt{5 x-1}}{\sqrt{x-1}}+1\right).
$$
Since $F(0) = w_0 = 0$, we see that the first root is the correct expression for $F(x)$, and so
$$
F(x) = \frac{1}{2} \left(1-\frac{\sqrt{5 x-1}}{\sqrt{x-1}}\right).
$$
Unfortunately there is unlikely to be a closed form series expression for $F$. Mathematica only returns something in the form of $\texttt{DifferenceRoot}$ and the first few terms
$$
0,1,2,5,15,51,188,731,2950,12235,51822,223191
$$
didn't match anything on OEIS.
</s>