0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

By looking at the first few terms and using the gfun package in Maple, it appears that the generating function of your sequence is

$$ g(x) = \sum_{n=1}^\infty \omega_n x^n = 1 - \sqrt{\frac{1-3x}{1-x}} $$

$\endgroup$
  • $\begingroup$ I don't have that software, could you confirm the following values hold? $\omega _7 = 96$, $\omega _{15} = 440915$. $\endgroup$ – Samuel Alonso Feb 25 '19 at 20:28
  • $\begingroup$ No, I get $\omega_7 = 753/16$ and $\omega_{15} = 184704489/2048$. Are you sure you wrote the recurrence correctly? $\endgroup$ – Robert Israel Feb 25 '19 at 20:30
  • $\begingroup$ Then it doesn't work :( Direct computation shows those values are correct, and I've confirmed them by hand. $\endgroup$ – Samuel Alonso Feb 25 '19 at 20:31
  • $\begingroup$ What are your values for $\omega_2$ to $\omega_6$? $\endgroup$ – Robert Israel Feb 25 '19 at 20:35
  • 1
    $\begingroup$ See OEIS sequence A300443. $\endgroup$ – Robert Israel Feb 25 '19 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.