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
On
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.$$
On
$f(1)=0$; $f(n)=3f(n-1)+12(-1)^n=3\Big(3f(n-2)+12(-1)^{n-1}\Big)+12(-1)^n$
For $n\ge 3$ you have
$$\begin{align*} f(n)&=3f(n-1)+12(-1)^n\\ &=3\Big(3f(n-2)+12(-1)^{n-1}\Big)+12(-1)^n\\ &=9f(n-2)+36(-1)^{n-1}+12(-1)^n\\ &=9f(n-2)+12(-1)^{n-1}\Big(3+(-1)\Big)\\ &=9f(n-2)+24(-1)^{n-1}\\ &=9f(n-2)-24(-1)^n\\ &=\begin{cases}9f(n-2)-24,&\text{if }n\text{ is even}\\ 9f(n-2)+24,&\text{if }n\text{ is odd}\;.\end{cases} \end{align*}$$
Now you can solve separately for the even and odd subsequences.
Let $a_0=0$ and $a_{n+1}=9a_n+24$ for $n\ge 0$. Substitute $b_n=a_n-d$ for some as yet unknown $d$, so that $a_n=b_n+d$, and the recurrence becomes $b_{n+1}+d=9(b_n+d)+24=9b_n+9d+24$, or $b_{n+1}=9b_n+8d+24$. If we set $d=-3$, this becomes $b_{n+1}=9b_n$, a simple exponential sequence whose solution has the closed form $b_n=9^nb_0$. And since $b_0=a_0-(-3)=3$, we immediately find the closed form $b_n=3\cdot9^n=3^{2n+1}$, whence $a_n=b_n+d=3^{2n+1}-3$. Now check that $f(2n+1)=a_n$, and you’ll see that $f(2n+1)=3^{2n+1}-3$. In other words, $f(n)=3^n-3$ when $n$ is odd.
You can handle the even subsequence similarly. You find that $d=3$, $b_n=9^{n-1}b_1=9^n$ (since $b_1=a_1-3=9$), and $a_n=9^n+3$. But $a_n=f(2n)$, so $f(2n)=9^n+3=3^{2n}+3$, i.e., $f(n)=3^n+3$ when $n$ is even. Combining the two, we have $f(n)=3^n-3(-1)^n$.
On
Let's write up a few more terms of the sequence to maybe guess a pattern. It goes $$0, 12, 24, 84, 240, 732 \cdots $$
Also keep in mind we expect these numbers to look something like powers of 3, because that's what the solution would be if we didn't have that $12(-1)^n$ term in the recurrence. So then with this hint we can see the terms are $$ 3^1-3, 3^2+3, 3^3-3, 3^4+3, 3^5-3, 3^6+3 \cdots $$
so we can guess the solution is $f_n = 3^n + 3(-1)^n .$ Now let us prove out suspicions with mathematical induction. The base case $n=1$ is true. Assume $f_n = 3^n + 3(-1)^n$ is true for some $n.$ Then $f_{n+1} = 3f_n - 12(-1)^n = 3( 3^n + 3(-1)^n ) - 12(-1)^n = 3^{n+1} -3(-1)^n = 3^{n+1} + 3(-1)^{n+1}$ so our formula is true for $n+1$ as well, completing the induction step.
On
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} \,.$$
On
Let $$g_n=(-1)^nf_n$$ then the $g_n$ satisfy $$g_n=-3g_{n-1}+12$$ Now let $$h_n=g_n-3$$ so $$\begin{align} h_n &= g_n-3 \\ &=(-3g_{n-1}+12)-3\\ &=-3(h_{n-1}+3)+9 \\ &=-3h_{n-1} \end{align}$$
So $$h_n=(-3)^{n-1}h_1$$
since $g_2=12$ so $h_2=9, h_1=-3$ and thus $$f_n=(-1)^n(h_n+3)=3^{n}+3(-1)^n$$.
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.