How to get the theta order of a non-homogeneous recurrence of Fibonacci sequence

Question

I'm recently learning recurrence and I'm stuck with how to find the theta order of a non-homogeneous Fibonacci sequence.

Given a Fibonacci sequence $F(N) = F(N-1)+F(N-2)+f(N)$. How can I determine the theta-order of this Fibonacci sequence if $f(N) = 1$? And what about $f(N) = N$?

I assume $F(0) = c_0$ and $F(1) = c_1$, and when $f(n) = 1$, I get $F(2) = c_0+c_1+1$, $F(3) = c_0+2 c_1+2$, $F(4) = 2 c_0+3 c_1+4$. And when $f(n) = n$, I get $F(2) = c_0+c_1+2$, $F(3) = c_0+2 c_1+3$, $F(4) = 2 c_0+3 c_1+4$. From these I think maybe there are some relations between $f(N) = N$ and $f(N) = 1$?

Answer 1

Case $f(n) = n$

We have $$F(n) = F(n-1)+F(n-2)+n$$ $$\Longleftrightarrow F(n)+ n + 3 = \left(F(n-1) + (n-1)+3\right)+\left(F(n-2) + (n-2)+3\right)$$ Denote $G(n) = F(n)+n+3$, then $G(n)$ is a Fibonacci sequence with $G(n) = G(n-1)+G(n-2)$. By consequence, $$F(n) = G(n) - n-3 = A\varphi^n + B\varphi^{-n} - n-3$$ with the coefficients $A,B$ defined from the 2 initial values of $F(n)$.

Case $f(n) = 1$

$$F(n) = F(n-1)+F(n-2)+1$$ $$\Longleftrightarrow F(n)+ 1 = \left(F(n-1) +1\right)+\left(F(n-2) +1\right)$$ Denote $H(n) = F(n)+1$, and with same argument as in the case 1, we have $$F(n) = H(n) -1 = A'\varphi^n + B'\varphi^{-n} - 1$$ with the coefficients $A',B'$ defined from the 2 initial values of $F(n)$.

Answer 2

It should not be too difficult to show that the difference equation $$ \phi_{n} = \phi_{n-1} + \phi_{n-2} + f_{n},$$ with the conditions $\phi_{0} = c_{0}$ and $\phi_{1} = c_{1}$, has the solution $$ \phi_{n} = \begin{cases} (c_{0}+1) \, F_{n+1} + (c_{1} - c_{0}) \, F_{n} - 1 & f_{n} = 1 \\ (c_{0}+6) \, F_{n+1} + (c_{1} - c_{0} + 2) \, F_{n} - (n+3) & f_{n} = n \end{cases} $$ where $F_{n}$ is the $n^{th}$ Fibonacci number.