# Thread: Linear Recurrence Relations.

1. ## Linear Recurrence Relations.

I have been cruising through this weeks lecture until I reached this section.
I will not lie, I am completely, utterly, and perhaps hopelessly lost on this topic. I begin getting lost pretty much immediately.

One example from the books states:

$a_n=a_{n-1}+2a_{n-2}$

with $a_0=2$ and $a_1=7$

I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

This then translates into problems of higher degree. Such as:

$a_n=6a_{n-1} - 11a_{n-2} + 6a_{n-3}$

Initial conditions $a_0=2, a_1=5, a_2=15$

2. Originally Posted by Nickolase
I have been cruising through this weeks lecture until I reached this section.
I will not lie, I am completely, utterly, and perhaps hopelessly lost on this topic. I begin getting lost pretty much immediately.

One example from the books states:

$an=an-1+2an-2$

with $a0=2$ and $a1=7$

I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

This then translates into problems of higher degree. Such as:

$an=6an-1 - 11an-2 + 6an-3$

Initial conditions $a0=2, a1=5, a2=15$
Your writing is decipherable but not very pleasant to read. I'm rewriting with using the underscore character (which on my keyboard is shift-hyphen where the hyphen key is to the right of 0) and braces to get subscripts.

~~~~~~~~~~~~~~~~~~~~

$a_n=a_{n-1}+2a_{n-2}$

with $a_0=2$ and $a_1=7$

I feel that if I had the correct procedures down I could do the work. Any help please and thanks.

This then translates into problems of higher degree. Such as:

$a_n=6a_{n-1} - 11a_{n-2} + 6a_{n-3}$

Initial conditions $a_0=2, a_1=5, a_2=15$

~~~~~~~~~~~~~~~~~~~~

Haven't looked at the problem yet, just thought people might like to see it properly formatted.

Edit: Hmm looks like you fixed it in the meantime..

3. Originally Posted by Nickolase
$a_n=a_{n-1}+2a_{n-2}$

with $a_0=2$ and $a_1=7$

4. Hello, Nickolase!

Here is one procedure for recurrence relations.
I'll solve the second problem.

$a_n \:=\:6a_{n-1} - 11a_{n-2} + 6a_{n-3}$

Initial conditions: $a_0=2, \;a_1=5,\;a_2=15$

We assume that $a_n$ is an exponential function.
. .
Let $X^n = a_n$.

We have: . $X^n \:=\:6X^{n-1} - 11X^{n-2} + 6X^{n-3}$

. . or: . $X^n - 6X^{n-1} + 11X^{n-2} - 6X^{n-3} \;=\;0$

Divide by $X^{n-3}\!:\;\;X^3 - 6X^2 + 11X - 6 \;=\;0$

. . Factor: . $(X-1)(X-2)(X-3) \;=\;0$

. . Hence: . $X \:=\:1,\:2,\:3$

The function is of the form: . $f(n) \;=\;A\!\cdot\!1^n + B\!\cdot\!2^n + C\!\cdot\!3^n$

We know the first three terms of the sequence:

$\begin{array}{ccccccccc}
f(0) = 2\!: & A + B + C &=& 2 & [1] \\
f(1) = 5\!: & A + 2B + 3C &=& 5 & [2] \\
F(2) = 15\!: & A + 4B+ 9C &=& 15 & [3] \end{array}$

$\begin{array}{cccccccc}
\text{Subtract [2] - [1]:} & B + 2C &=& 3 \\
\text{Subtract [3] - [2]:} & 2B + 6C &=& 10 \end{array}$

Solve this system of equations: . $B = -1,\;C = 2$

Substitute into [1]: . $A - 1 + 2 \:=\:2 \quad\Rightarrow\quad A \:=\:1$

Therefore, the generating function is:

. . $f(n) \;=\;1 - 2^n + 2\!\cdot\!3^n$

5. Originally Posted by undefined