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.

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, let alone how to solve it:

Determine $a_n$ as given by:

$a_n$ = $a_{n-1}$ + $6a_{n-2}$; $a_0 = 1$, $a_1 = 8$

There are a series of problems like this and once I figure out what it is and how to solve it, I can go watch some MIT videos and learn about it and then solve the rest. But first I need to know what exactly I'm trying to do. Any help would be greatly appreciated.

I can't even properly tag the question. :)

share|improve this question
4  
$a_n$ is determined by a recurrence relation. –  Michael Albanese Sep 29 '12 at 16:26

4 Answers 4

up vote 2 down vote accepted

In general, for a given recurrence relation of the form $x_n+a_1x_{n-1}+\cdots+a_{r}x_{n-r}=k^nf(n)$, where $a_1,...,a_r,k$ are given constants and $f(n)$ is a polynomial in $n$, and assuming you are given $x_0,\ldots,x_{r-1}$, then you can solve this in two steps:
Step 1: define the characteristic polynomial to be $t^r+a_1t^{r-1}+\cdots+a_0$. Let $t_1,\ldots,t_r$ be all the roots (over $\mathbb{C}$). If they are all distinct, then you write $x_n^{(h)}=\alpha_1t_1^n+\cdots+\alpha_rt_r^n$ - the homogeneous part. If you have multiplicity $s$ to some root $t_j$ then you replace it's appearances in the solution with $(n^{s-1}\beta_1+\cdots+b_{s})t_j^n$.
Step 2: $x_n^{(p)}=k^nn^sg(n)$ where $k$ is the same, $s$ is the multiplicity of $k$ as a root of the characteristic polynomial defined above (if $k$ is not a root, then $s=0$) and $g(n)$ is a polynomial of the same degree as $f(n)$.
Now $x_n=x_n^{(h)}+x_n^{(p)}$. Substituting back and using the given $x_0,\ldots,x_{r-1}$ you can find the constants.

Now, apply this method to your problem: $a_n-a_{n-1}-6a_{n-2}=0$, $a_0=1, a_1=8$.
The characteristic polynomial will be $t^2-t-6=(t-3)(t+2)$. Hence $a_n^{(h)}=\alpha 3^n +\beta (-2)^n$. Since $f(n)=0$ we have $a_n^{(p)}=0$.
Now we just need to use the initial values: $$\begin{array}{c} a_0=\alpha+\beta=1 \\ a_1=3\alpha-2\beta=8\end{array} \Rightarrow \begin{array}{c} \alpha+\beta=1 \\ 5\alpha=10\end{array} \Rightarrow \begin{array}{c} \beta=-1 \\ \alpha=2\end{array} $$ Finally, $a_n=2\cdot 3^n - (-2)^n$

share|improve this answer
    
Perfect, thanks mate. Looks like I have some studying ahead of me. –  AWT Sep 30 '12 at 18:58

This is a recurrence relation (also called a difference equation). It recursively defines all $a_n$. First, plug in $a_0$ for $a_{n-2}$ and $a_1$ for $a_{n-1}$. This gives you $a_n$, which corresponds to $a_2$. Go through the equation again, this time with $a_1$ and $a_2$ to get $a_3$, and so on until you have all $a_n$. This kind of program is great for computers because you can write a simple loop to do this.

share|improve this answer
    
Thanks. Fixed it. –  Andy Harris Sep 29 '12 at 17:35

It is called a recursive sequence, sequence of numbers, this goes like $1,8,8+6\cdot 1=14,14+6\cdot 8,\dots$ applying $a_n=a_{n-1} + 6a_{n-2}$ by substituting $2$ and $3$ into the index $n$. Got it?

Then these kind of so called linear recursions can be explicitly written in a form something like $a_n=C\cdot u^n + D\cdot v^n$ for some numbers $C,D,u,v$. And finding these starts by looking for geometric sequences satisfying the recursion condition: So, find $q$ such that $q^n$ satisfies $q^n=q^{n-1}+6\cdot q^{n-2}$ for all $n=2,3,4,5,\dots$.

share|improve this answer
1  
"substituting 2 and 3 into the index n" is a confusing statement. –  zyx Sep 29 '12 at 16:37

This is an example of a linear recurrence relation. It is a rule that generates an infinite sequence of numbers. To know which number comes next, you add the previous number to six times the last-but-one number: $a_n = a_{n-1} + 6a_{n-2}.$ You are also told that $a_0 = 1$ and $a_1 = 8.$ Thus $a_2 = a_1 + 6a_0 = 14$, $a_3 = a_2 + 6a_1 = 62,$ etc.

Standard techniques exist for solving such recurrence relations. In this case:

$$a_n = 2\times 3^n - (-2)^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.