I have a recursive formula for a sequence O: $ O_n = O_{n-1} + O_{n-2} + F_{n-1}$ where $F_n$ is the n-th Fibonacci number, $O_1 = 1$ and $O_2 = 2$.

After playing around with it, I found a new formula that might be easier to convert to the form I search: $ O_n = F_{n-3} * O_1 + F_{n-2} * O_2 + \sum_{k=2}^{n-1} F_{n-1-k} * F_k$.

Now what I am searching for is an explicit formula for $O_n$ that doesn't include a summation.

I also tried filling in Binet's formula and simplify, to no avail.

Here's a similar post, but the math is too hard for me, so I can't transform it to fit my problem.

An interesting property I found is that $\lim_{x\to\infty} \frac{O_x}{O_{x-1}}$ is equal to the golden ratio.

  • $\begingroup$ Try a term like $nF_n$ $\endgroup$ – Empy2 Jul 5 '20 at 14:27
  • $\begingroup$ This is A029907. There is some discussion on the linked page, in particular you can find the claim that $O_n=\frac {(n+4)F_n+2nF_{n-1}}5$ which should be easy to verify. $\endgroup$ – lulu Jul 5 '20 at 14:27
  • 1
    $\begingroup$ As another approach, it follows immediately from your definition that $O_n$ satisfies $O_n=2O_{n-1}+O_{n-2}-2O_{n-3}-O_{n-4}$ and the associated characteristic polynomial factors as $(x^2-x-1)^2$. $\endgroup$ – lulu Jul 5 '20 at 14:34

I calculated a few terms and got $(O_n)=(1,2,4,8,15,28,51...)$.

I looked this up in OEIS and found this formula, which could be made explicit with Binet's formula:



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.