How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

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

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} \,.$$

I didn't see anyone using generating functions yet, so I'll use them for no other reason than they're fun.

You are trying to solve the recurrence with $f_0=0$ and $f_k=3f_{k-1}+12(-1)^{k+1}$ for all $k\in\mathbb{Z}^{+}$.

Let $F(x)=\sum_{k\geq0}f_kx^k$ be the generating function of the sequence defined by the given recurrence.

$\begin{align} F(x) &= \sum_{k\geq0}f_kx^k\\ &= f_0x^0+\sum_{k\geq1}f_kx^k\\ &= \sum_{k\geq1}(3f_{k-1}+12(-1)^{k+1})x^k\\ &= \sum_{k\geq1}3f_{k-1}x^k+\sum_{k\geq1}12(-1)^{k+1}x^k\\ &= 3x\sum_{k\geq0}3f_kx^k+12x\sum_{k\geq0}(-1)^kx^k\\ &= 3xF(x)+\frac{12x}{1+x}\\ \end{align}$

Now we may solve for $F(x)$ and obtain $F(x)=\frac{12x}{(1+x)(1-3x)}=\frac{3}{1-3x}-\frac{3}{1+x}$.

To find the closed form for the recurrence, we may expand $F(x)$ about the point $x_0=0$.

$\begin{align} F(x) &= \frac{3}{1-3x}-\frac{3}{1+x}\\ &= 3\sum_{k\geq0}3^kx^k-3\sum_{k\geq0}(-1)^kx^k\\ &= \sum_{k\geq0}(3^{k+1}-3(-1)^k)x^k\\ \end{align}$

So the closed form for the recurrence is $f_k=3^{k+1}-3(-1)^k$, for all non-negative $k$.

The original recurrence used an initial index of one rather than zero. Then the closed form becomes $f_k=3^k-3(-1)^{k-1}$, for all positive $k$.

EDIT: OP mentioned that he is not familiar with generating functions, so here is a link the generatingfunctionology.

Let $g_n=f_n-3(-1)^n$, i.e. $f_n=g_n+3(-1)^n$. Then $$ g_n = f_n-3(-1)^n = 3f_{n-1}-3(-1)^n +12(-1)^n\\= 3g_{n-1}+9(-1)^{n-1}-3(-1)^n +12(-1)^n=3g_{n-1},$$ Thus $g_n=3^{n-1}g_1$ and ultimately $$ f_n = 3^{n-1}g_1-3(-1)^n = 3^{n-1}(f_1+3)-3(-1)^n=3^n-3(-1)^n.$$