How do i solve the recurrence: $f(n)=F(n-1)+f(n-2)+1$?
My first attempt was to "guess" a private solution to the nonhomogenous which got me : $ f(n)= -1 $ and the corresponding is $F_n$ (fibonacci), so the exact solution is $ f(n)=F_n -1$?
was it right? thanks in advance.
In this case, inspired guessing is probably best; but if you want a systematic method: these three instances of the initial recurrence \begin{align*} -f(n)+F(n-1)+f(n-2)+1=0 \\ -f(n+1)+F(n)+f(n-1)+1=0 \\ f(n+2)-F(n+1)-f(n)-1=0 \end{align*} sum to $$ f(n+2) - f(n+1) -2f(n)+ f(n-1) + f(n-2) + 1 = 0. $$ Subtracting this from its shifted version $$ f(n+3) - f(n+2) -2f(n+1)+ f(n) + f(n-1) + 1 = 0 $$ yields $$ f(n+3) - 2f(n+2) - f(n+1) + 3f(n) - f(n-2) = 0. $$ This can be solved with the usual linear recurrence methods: its characteristic equation is $x^5 - 2 x^4 - x^3 + 3 x^2 - 1 = (x-1)^2 (x+1) (x^2-x-1)$, and so the general solution is $$ f(n) = A + Bn + C(-1)^n + D\phi^n + E(-\phi)^{-n}, $$ where $\phi=(1+\sqrt5)/2$ and $-\phi^{-1}$ are the roots of $x^2-x-1$.