How to get the theta order of a non-homogeneous recurrence of Fibonacci sequence 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$?
 A: 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)$.
A: 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.
