Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Also I am not sure whether this recurrence is solvable because after trying a lot I still couldn't get the answer –  user43255 Oct 1 '12 at 11:07
    
@Michael :can you suggest a solution? Is it solvable? –  user43255 Oct 1 '12 at 11:13
2  
Yes it's not so bad. Do you know about generating functions? –  Ragib Zaman Oct 1 '12 at 11:13
    
@RagibZaman:no sir –  user43255 Oct 1 '12 at 11:14
    
@RagibZaman:I was trying to solve by repetitive substitution till I reached the base case...But I wasn't able to get the solution –  user43255 Oct 1 '12 at 11:15

6 Answers 6

up vote 7 down vote accepted

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.

share|improve this answer
1  
A useful method. Even when the "tricks" in the other cases don't work, this still might work. –  GEdgar Oct 1 '12 at 17:41

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

share|improve this answer
    
@Graphth: Thank you! –  Mhenni Benghorbal Oct 1 '12 at 16:31

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.$$

share|improve this answer
    
This is excellent. –  Michael Albanese Oct 1 '12 at 11:25
    
Shouldn't that be $f_n=3^{n-1}g_1+3(-1)^n=\;\cdots\;=3^n+3(-1)^n?$ Nice solution by the way. –  user39572 Oct 1 '12 at 11:32

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.

share|improve this answer

$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$.

share|improve this answer

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$$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.