Need Help with Mistake in Generating Function for Nonlinear Recurrence relation

Question

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 🙂

Answer 1

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.