How to solve a recurrence relation with a constant factor?

Question

How do you solve a linear recurrence relation with a constant factor? For example, given the sequence

$f(n)=f(n-2)+f(n-1)+1$

how do you find the characteristic equation? When I try to solve

$r^n=r^{n-2}+r^{n-1}+1 $

I can’t factor out a term to solve for r.

Answer 1

Assume $g(n) = f(n)+1$, then $f(n)= f(n-1)+f(n-2)+1 \implies g(n)-1=g(n-1)-1+g(n-2)-1+1 \implies g(n)=g(n-1)+g(n-2)$ Characteristic equation for this recurrence: $r^n = r^{n-1}+r^{n-2} \implies r^2=r+1 \implies r = \frac{1 \pm \sqrt{5}}{2}$

Therefore $f(n)=g(n)-1=c_0 \cdot (\frac{1 + \sqrt{5}}{2})^n+c_1 \cdot (\frac{1 - \sqrt{5}}{2})^n-1$, for some $c_0$ and $c_1$.

Answer 2

Say that you have $$f_n=af_{n-1}+bf_{n-2}+c$$ Let $f_n=g_n+k$ and replace $$g_n+k=a g_{n-1}+a k+b g_{n-2}+b k+c$$ Make $$k=ak+bk+c\implies k=-\frac{c}{a+b-1}$$ to end with $$g_n=a g_{n-1}+b g_{n-2}$$ Solve it and go back to $f_n$.