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$?

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)$.
