1. ## Recurrence Relations

I have been working on this problem but I cant find anything similar in my book. Not sure how to setup this problem.

Solve the following recurrence relations together with the initial conditions given. $\displaystyle a_n=2a_{n-1}+3a_{n-2}$ for $\displaystyle n\ge 2$, $\displaystyle a_0=1, a_1=7$. Thanks in advance for the help.

2. We have $\displaystyle a_{n+2} = 2a_{n+1} + 3a_n => a_{n+2} - 2a_{n+1} - 3a_n = 0$

Now set $\displaystyle a_n = w^n$ so we now have...

$\displaystyle w^{n+2} - 2w^{n+1} - 3w^{n} = 0$

$\displaystyle w^2 - 2w - 3 = 0$

Then solve for w and we get w=3 and w=-1.

Then put this into the general equation $\displaystyle u_n = c_1 \cdot 3^n + c_2 \cdot (-1)^n$.
Then use your initial conditions to find the constants.

3. I don't really understand what you have done. I have been reading this book and still dont get it.

4. Originally Posted by alexriverajr
I don't really understand what you have done. I have been reading this book and still don’t get it.
And you will not never ‘get it’ until you practice on many of these.
So, use what you were given and solve for $\displaystyle c_1~\&~c_2$.
Then use that example and do several more.

We have $\displaystyle a_{n+2} = 2a_{n+1} + 3a_n => a_{n+2} - 2a_{n+1} - 3a_n = 0$ (1)

Now set $\displaystyle a_n = w^n$ so we now have...

$\displaystyle w^{n+2} - 2w^{n+1} - 3w^{n} = 0$

$\displaystyle w^2 - 2w - 3 = 0$

Then solve for w and we get w=3 and w=-1. (2)

Then put this into the general equation $\displaystyle a_n = c_1 \cdot 3^n + c_2 \cdot (-1)^n$. (3)
Then use your initial conditions to find the constants. (4)
(1) Since $\displaystyle a_{n} = 2a_{n-1} + 3a_{n-2}$ then
$\displaystyle a_{n+2} = 2a_{n+1} + 3a_{n}$ since i doesnt matter whether we have n, n+2 or n+145334544 the relation is still the same...
In general, $\displaystyle a_{n+k} = 2a_{n+(k-1)} + 3a_{n+(k-2)}$

(2) Just solve the polynomial for w.

(3) The general equation is $\displaystyle a_n = c_1 \cdot w_1^n + c_2 \cdot w_2^n$ with the w terms being what you found in (2) and the c terms are constants you can find if you have initial conditions.

(4) The initial conditions state that $\displaystyle a_0 = 1$ and $\displaystyle a_1 = 7$, This means that when $\displaystyle n=0, a_n = 1$, hence if you sub this into the equation found in (3), you get that $\displaystyle 1 = c_1 \cdot 3^0 + c_2 \cdot (-1)^0 = c_1 + c_2$
Then sub the other initial condition in... $\displaystyle 7 = c_1 \cdot 3^1 + c_2 \cdot (-1)^1$... Solve this and you'll get two equations containing $\displaystyle c_1$ and $\displaystyle c_2$. You should be able to find the c's from there and then you have the general solution.

I also just noticed that i had $\displaystyle u_n$ in my first post instead of $\displaystyle a_n$, maybe that confused you?

To test yourself look up gamblers ruin and try to solve it. Its similar to this.

6. Originally Posted by alexriverajr
I have been working on this problem but I cant find anything similar in my book. Not sure how to setup this problem.

Solve the following recurrence relations together with the initial conditions given. $\displaystyle a_n=2a_{n-1}+3a_{n-2}$ for $\displaystyle n\ge 2$, $\displaystyle a_0=1, a_1=7$. Thanks in advance for the help.
Or you could use generating functions. Let $\displaystyle F(x) = \sum_{n \geq 0} a_{n}x^n = a_0+a_{1}x+a_{2}x^2+a_{3}x^{3} + \cdots$. Now multiply the LHS and RHS of the recurrence relation by $\displaystyle x^n$ and sum over $\displaystyle n$. We get $\displaystyle \sum_{n \geq 2} a_{n}x^{n} = 2 \sum_{n \geq 2} a_{n-1}x^{n} + 3 \sum_{n \geq 2} a_{n-2}x^n$. Now the key idea is to represent this by $\displaystyle F(x)$. So $\displaystyle a_{2}x^{2}+a_{3}x^{3} + \cdots = 2(a_{1}x^{2}+a_{2}x^{3}+a_{3}x^2 + \cdots )+3(a_{1}x^3+a_{2}x^{4} + \cdots)$. Thus $\displaystyle F(x)-1-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}$.

Now solve for $\displaystyle F(x)$. We get $\displaystyle F(x)-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}+1$. So $\displaystyle F(x)-2xF(x)-3x^{2}F(x) = -3x^{2}+5x+1$. Or $\displaystyle F(x)(1-2x-3x^2) = -3x^2+5x+1$. Thus $\displaystyle F(x) = \frac{-3x^2+5x+1}{1-2x-3x^2}$.

7. Thanks all. Your help is really appreciated.