# Help with Nonlinear Recurrence Relation

Hello guys :) I've got a bit of an issue with the following recurrence relation:

Let $$\omega _1 = 1$$. Now, let $$\omega _n$$ be defined as follows $$w_n = 1 + \sum _{k=1}^{n-1}C^{k}_{n-k} \, \omega _k \, \omega _{n-k}$$ where $$C^{k}_{n-k} = \frac{1+\delta^{k}_{n-k}}{2} = \left\lbrace \begin{array}{l l} 1/2, & n \neq n-k \\ 1, & n= n-k \end{array} \right.$$ My goal was to (at least attempt) to find a closed form for $$\omega _n$$, but it has proven quite difficult for me. I've tried rewriting the term $$C^{k}_{n-k} \, \omega _k \, \omega _{n-k}$$ as the application of a bilinear form, approximating the sum as a weighted convolution by setting $$\omega _0 = 0$$ artificially, and some other things but it just won't budge. To be honest, my repertoire of recurrence tricks isn't too vast, and I've read online that only a few classes of nonlinear recurrence relations actually have a closed form. Any help and kind observations would be appreciated :)

$$g(x) = \sum_{n=1}^\infty \omega_n x^n = 1 - \sqrt{\frac{1-3x}{1-x}}$$
• I don't have that software, could you confirm the following values hold? $\omega _7 = 96$, $\omega _{15} = 440915$. – Samuel Alonso Feb 25 '19 at 20:28
• No, I get $\omega_7 = 753/16$ and $\omega_{15} = 184704489/2048$. Are you sure you wrote the recurrence correctly? – Robert Israel Feb 25 '19 at 20:30
• What are your values for $\omega_2$ to $\omega_6$? – Robert Israel Feb 25 '19 at 20:35