2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I think the $-x$ term should be $+1$. $\endgroup$
    – WimC
    Jan 19, 2020 at 7:12
  • $\begingroup$ 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? $\endgroup$ Jan 19, 2020 at 7:16
  • $\begingroup$ 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. $\endgroup$ Jan 19, 2020 at 7:43
  • $\begingroup$ 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}.$$ $\endgroup$
    – WimC
    Jan 19, 2020 at 11:52

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Jan 19, 2020 at 16:43
  • $\begingroup$ Indeed that was a typo, so I fixed it. But it didn't change the result as $w_0=0$. $\endgroup$
    – Math1000
    Jan 19, 2020 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 20, 2020 at 1:06
  • $\begingroup$ 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}} $$ $\endgroup$
    – Math1000
    Jan 20, 2020 at 1:30
  • $\begingroup$ 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. $\endgroup$ Jan 20, 2020 at 2:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .