# 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 :)

• I think the $-x$ term should be $+1$.
– WimC
Jan 19, 2020 at 7:12
• Why should it be $+1$? That term comes from $-(w_0 + w_1 x)$, and since $w_0 = 0$, $w_1 = 1$, the resulting term is $-x$. Could you elaborate? Jan 19, 2020 at 7:16
• The error is, I think, in the RHS: it should be $F(x)^2-1$. You have summed the RHS from $0$ to $\infty$ but the formula is only true for $n\geqslant 2$ so you have to patch on $w_1 x-x$ and $w_0-1$ as the first two terms, to ensure RHS=LHS. Jan 19, 2020 at 7:43
• Note that the recurrence in fact holds for $n\geq 1$. But see also the answer of math1000 since $$x + \frac{x^2}{1-x}=-1+\frac1{1-x}.$$
– WimC
Jan 19, 2020 at 11:52

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.
• Thank you for your answer! However, I just noticed that on your first line, you've set the sum of the $w_k w_{n-k}$ to be from $1$ to $n$, instead of $1$ to $n-1$ as in the recurrence's definition. Could it be a typo? Jan 19, 2020 at 16:43
• Indeed that was a typo, so I fixed it. But it didn't change the result as $w_0=0$. Jan 19, 2020 at 17:14
• After some lengthy computations, turns out that there is a closed form! The $n$-th derivatives of $(5x-1)^{1/2}$ and $(x-1)^{-1/2}$ can easily be computed, and everything can be collected at the end using the Leibniz rule. Jan 20, 2020 at 1:06
• I get $$\frac{\mathsf d^n}{\mathsf dx^n} (5x-1)^{1/2} = \left(\frac 5{5x-1}\right)^n (5x-1)^{-1/2}\prod_{i=0}^{n-1}\left(\frac12-i\right)$$ and $$\frac{\mathsf d^n}{\mathsf dx^n} (x-1)^{-1/2} = (x-1)^{-(n+1/2)}\prod_{i=0}^{n-1}(-1/2-i),$$ so $$F^{(n)}(x) = -\sum_{k=0}^n\binom nk \left(\frac 5{5x-1}\right)^{n-k} (5x-1)^{-1/2}\prod_{i=0}^{n-k-1}\left(\frac12-i\right)(x-1)^{-(k+1/2)}\prod_{i=0}^{k-1}(-1/2-i),$$ equal to $$\frac{5^n \left(\frac{1}{2}\right)^{(n)} (5 x-1)^{\frac{1}{2}-n} \, _2F_1\left(\frac{1}{2},-n;\frac{3}{2}-n;\frac{1}{25 x^2-30 x+5}\right)}{\sqrt{x-1}}$$ Jan 20, 2020 at 1:30
• Recall you must evaluate at $x=0$ to get the expansion coefficients :) After all, it formally is a power series around $x=0$. (Also, don't miss the sneak y $(n!)^{-1}$). On another note, the formula looks much cleaner using double factorials. Consider using them instead of the prods. Jan 20, 2020 at 2:00