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:

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

with $\displaystyle a_0=2$ and $\displaystyle 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:

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

Initial conditions $\displaystyle 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:

$\displaystyle an=an-1+2an-2$

with $\displaystyle a0=2$ and $\displaystyle 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:

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

Initial conditions $\displaystyle 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.

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

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

with $\displaystyle a_0=2$ and $\displaystyle 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:

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

Initial conditions $\displaystyle 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
$\displaystyle a_n=a_{n-1}+2a_{n-2}$

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

4. Hello, Nickolase!

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

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

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

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

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

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

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

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

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

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

We know the first three terms of the sequence:

$\displaystyle \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}$

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

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

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

Therefore, the generating function is:

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

5. Originally Posted by undefined