How to solve this particular recurrence relation ?
$$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$
such that $f_2 = 12, f_3 = 24$ and so on.
I tried out a lot but due to $(-1)^n$ I am not able to solve this recurrence?
Any help will be highly appreciated.
Please this is no homework. I came across this while solving a problem on SPOJ
Best Answer
Here is a systematic way to solve it,
$$ f_n - 3f_{n-1} - 12(-1)^n =0\,. $$
Shifting $n$ in the above equation gives
$$ f_{n+1} - 3f_{n} + 12(-1)^n =0\,. $$
add the two equations results in the homogeneous difference equation
$$ f_{n+1} -2 f_{n} - 3 f_{n-1} =0 $$
Now, we can solve the above recurrence relation, subject to the initial conditions $f_{0}=0$ and $f_2 = 12 $, which is equivalent to the original one. To solve it, just assume the has the form $f_n=r^n$ and substitute back into the difference equation and solve for $r$. Finding the roots of roots of the resulting polynomial in $r$ gives the solution
$$f_n = c_1 (-1)^n+c_2 3^n \,.$$
Exploiting the initial conditions gives
$$f_n = -3 (-1)^n+ 3^{n+1} \,.$$