4
$\begingroup$

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. :)

  • 4
    $a_n$ is determined by a *recurrence relation*.2012-09-29

4 Answers 4

1

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

3

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.

2

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$

  • 0
    Perfect, thanks mate. Looks like I have some studying ahead of me.2012-09-30
1

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

  • 1
    "substituting 2 and 3 into the index n" is a confusing statement.2012-09-29