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.

For the following, solve each of the following recurrence relations by giving explicit formula for $a_n$ and calculate $a_9$.
$a_n = 10 a_{n-1}, a_0 = 3; $
$a_n = -a_{n-1}, a_0 = 5;$
$a_n = 3 a_{n-1} - 1, a_0 = 10; $
$a_n = 4-2 a_{n-1}, a_0 = 0; $
$a_n = 8 a_{n-1} - 15a_{n-2}, a_0 = 1, a_1 = 4; $
$a_n = a_{n-1} +6a_{n-2}, a_0 = 4, a_1 = 4;$

Im trying to self teach my self discrete mathematics and I have just reached recurrence relations but im struggling with it. I was able to do others but im stuck. An clear explanation would be appreciated. There is over 100 exercises in my book so I want to be able to do the other ones my self.

For 3, I got $a_n=(19/2) (3)^n+1/2.$ $For a_9=186989$.
I believe this is correct. But im still struggling to solve for the other ones. Help would be appreciated.

For 1 and 2, I got $3(10)^n$ and $5(-1)^n$ respectively.

share|improve this question
    
To have more than one character in subscript, use braces {}. I've done this with a_{n-1} in your first line - I'll let you tackle the rest. –  alex.jordan Apr 5 '13 at 4:00
    
The first two might become clear if you just write out several terms. Have you tried that? –  alex.jordan Apr 5 '13 at 4:01
1  
What book are you using? Knowing that would give me a better idea of which techniques that you’re trying to learn at this point. –  Brian M. Scott Apr 5 '13 at 4:02
    
For the third and fourth, try substituting $a_n=b_n+c$. For the right values of $c$, they reduce to the form that you see in the first two. –  alex.jordan Apr 5 '13 at 4:03
    
For the fifth and sixth there are standard approaches, but they are not something I would have come up with on my own. Someone or some book taught me. –  alex.jordan Apr 5 '13 at 4:04

1 Answer 1

One way to solve the fourth problem is to ‘unwind’ the recurrence:

$$\begin{align*} a_n&=4-2a_{n-1}\\ &=4-2(4-2a_{n-2})\\ &=4-2\cdot4+2^2a_{n-2}\\ &=4-2\cdot4+2^2(4-2a_{n-3})\\ &=4-2\cdot4+2^2\cdot4-2^3a_{n-3}\\ &=4-2\cdot4+2^2\cdot4-2^3(4-2a_{n-4})\\ &=4-2\cdot4+2^2\cdot4-2^3\cdot4+2^4a_{n-4}\\ &\;\vdots\\ &=4-2\cdot4+2^2\cdot4-\ldots+(-1)^{k-1}2^{k-1}\cdot4+(-1)^k2^ka_{n-k}\\ &\;\vdots\\ &=4-2\cdot4+2^2\cdot4-\ldots+(-1)^{n-1}2^{n-1}\cdot4+(-1)^n2^na_0\\ &=4\sum_{k=0}^{n-1}(-1)^k2^k\\ &=4\sum_{k=0}^{n-1}(-2)^k\\ &=4\cdot\frac{(-2)^n-1}{-2-1}\\ &=-\frac43\left((-2)^n-1\right)\\ &=\frac43\left(1-(-2)^n\right) \end{align*}$$

I imagine starting with a large enough $n$ so that I can work back through several steps of the recurrence, and I try to find a pattern. Of course I might have guessed wrong, so at this point I really ought to prove by induction that if I define

$$b_n=\frac43\left(1-(-2)^n\right)\;,$$

then $b_n=a_n$ for all $n\ge 0$. Before doing that, I might make a quick check: this closed formula yields $a_0=0,a_1=4,a_2=-4$, and $a_3=12$, which are easily verified against the original recurrence, so it probably is right.

Another way to solve a first-order linear recurrence with a constant forcing term (the $+4$ in this recurrence) is to make a change of variable. Let $b_n=a_n+d$ for some as yet unknown constant $d$; we’ll choose $d$ so that $b_n$ satisfies a recurrence like the ones in your first two problems. Now $a_n=b_n-d$ (and of course $a_{n-1}=b_{n-1}-d$), which I substitute into the original recurrence to get

$$b_n-d=4-2(b_{n-1}-d)=4-2b_{n-1}+2d\;,$$

or $b_n=-2b_{n-1}+4+3d$. If I let $d=-\frac43$, this becomes $b_n=-2b_{n-1}$, which has the easy closed form solution $b_n=(-2)^nb_0$. And $b_0=a_0+d=-\frac43$, so $b_n=-\frac43(-2)^n$ for all $n\ge 0$. Finally, we reverse the substitution to get

$$a_n=b_n-d=-\frac43(-2)^n-\left(-\frac43\right)=\frac43\left(1-(-2)^n\right)\;.$$

More general techniques will also handle problems like this, but sometimes limited, elementary techniques are quicker.

$a_n = 8 a_{n-1} - 15a_{n-2}, a_0 = 1, a_1 = 4$

I’ll finish up with your fifth problem. The technique most often taught at the elementary level uses a so-called auxiliary equation; in principle this technique works whenever you have a linear homogeneous recurrence with constant coefficients.

To get the auxiliary equation, replace $a_n$ by $x^n$ (and similarly $a_{n-1}$ by $x^{n-1}$ and so on) to get $x^n=8x^{n-1}-15x^{n-2}$. Now divide through by the lowest power of $x$ appearing in the equation to get $x^2=8x-15$. Solve the equation: $0=x^2-8x+15=(x-3)(x-5)$, so the solutions are $r=3$ and $s=5$. This means that the general solution of the recurrence

$$x_n=8x_{n-1}-15x_{n-2}$$

is $$x_n=\alpha 3^n+\beta 5^n\;,\tag{1}$$ where the specific values of $\alpha$ and $\beta$ depend on $x_0$ and $x_1$.

Digression: In general, if the auxiliary equation has distinct solutions $r_1,\dots,r_m$, the general solution will be $x_n=\alpha_1 r_1^n+\ldots+\alpha_m r_m^n$, where the coefficients $\alpha_1,\dots,\alpha_m$ depend on the initial values $x_0,\dots,x_{m-1}$. If it has repeated roots, the general solution is a little different. For instance, if the auxiliary equation had been $x^2-4x+4=0$, the roots would have been $r=s=2$. In that case the general solution would have been $x_n=\alpha 2^n+\beta n2^n$, not $\alpha 2^n+\beta 2^n$, which, after all, is no more general than the single term $\alpha 2^n$, since the two terms can be combined. More generally, if a root $r$ appears $k$ times, it produces terms $$\alpha_1 r^n+\alpha_2 nr^n+\ldots+\alpha_k n^{k-1}r^n$$ in the general solution.

All that remains is to determine $\alpha$ and $\beta$ to get the right initial values. To do this, substitute $t=0$ and $t=1$ into $(1)$:

$$\left\{\begin{align*} &1=a_0=\alpha 3^0+\beta 5^0=\alpha+\beta\\ &4=a_1=\alpha 3^1+\beta 5^1=3\alpha+5\beta \end{align*}\right.$$

Solve this system by whatever means you prefer to find that $\alpha=\beta=\frac12$, so the solution is

$$a_n=\frac12\left(3^n+5^n\right)\;.$$

As a quick sanity check, this does yield the correct values $a_0=1,a_1=4,a_2=17$, and $a_3=76$.

You can now try this technique on the sixth problem.

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.