# Recursive to explicit form involving Fibonacci

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.

• Try a term like $nF_n$ – Empy2 Jul 5 '20 at 14:27
• 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. – lulu Jul 5 '20 at 14:27
• 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$. – lulu Jul 5 '20 at 14:34

I calculated a few terms and got $$(O_n)=(1,2,4,8,15,28,51...)$$.
$$O_n=\dfrac{(n+4)F_n+2nF_{n-1}}5.$$