how to solve following recurrence relation :
$f(n) = 3 * f(n - 1) + 4$
i've got that recurrence relation from following sequence, where f(n) is nth value of the following sequence.
$7, 25, 79, 241, 727, 2185$, and so on.
So $f(0) = 7$, $f(1) = 25$. etc.
The hint from Neat Math suggests $f(n)=3f(n-1)+4\iff f(n)+2=3(f(n-1)+2)$
or $g(n)=3g(n-1)$ where $g(n)=f(n)+2$, so $g(n)=3^{n}g(0)$, with $g(0)=9$,
so $g(n)=3^{n+2}$, so $f(n)=3^{n+2}-2$.
A more pedantic solution would be the following:
$f(n)-3f(n-1)=f(n-1)-3f(n-2)$, so $f(n)=4f(n-1)-3f(n-2)$.
The roots of the characteristic equation $r^2=4r-3$ are $r=1,3$,
so the solution is $f(n)=A\cdot3^n+B\cdot1^n$.
Solve for $A$ and $B$ given $f(0)=7$ and $f(1)=25$.