Recurrence Relations

**alexriverajr** · May 28th 2009, 02:28 PM

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. $a_n=2a_{n-1}+3a_{n-2}$ for $n\ge 2$ , $a_0=1, a_1=7$ . Thanks in advance for the help.

**Deadstar** · May 28th 2009, 03:05 PM

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

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

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

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

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

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

**alexriverajr** · June 6th 2009, 03:08 PM

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

**Plato** · June 6th 2009, 03:23 PM

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 $c_1~\&~c_2$ .
Then use that example and do several more.

**Deadstar** · June 6th 2009, 06:53 PM

Originally Posted by Deadstar

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

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

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

$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 $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 $a_{n} = 2a_{n-1} + 3a_{n-2}$ then
$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, $a_{n+k} = 2a_{n+(k-1)} + 3a_{n+(k-2)}$

(2) Just solve the polynomial for w.

(3) The general equation is $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 $a_0 = 1$ and $a_1 = 7$ , This means that when $n=0, a_n = 1$ , hence if you sub this into the equation found in (3), you get that $1 = c_1 \cdot 3^0 + c_2 \cdot (-1)^0 = c_1 + c_2$
Then sub the other initial condition in... $7 = c_1 \cdot 3^1 + c_2 \cdot (-1)^1$ ... Solve this and you'll get two equations containing $c_1$ and $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 $u_n$ in my first post instead of $a_n$ , maybe that confused you?

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

**Sampras** · June 6th 2009, 09:19 PM

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. $a_n=2a_{n-1}+3a_{n-2}$ for $n\ge 2$ , $a_0=1, a_1=7$ . Thanks in advance for the help.

Or you could use generating functions. Let $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 $x^n$ and sum over $n$ . We get $\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 $F(x)$ . So $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 $F(x)-1-7x = 2xF(x)-2x+3x^{2}F(x)-3x^{2}$ .

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

**alexriverajr** · June 7th 2009, 04:14 PM

Thanks all. Your help is really appreciated.

Thread: Recurrence Relations

LinkBack

Thread Tools

Display

Recurrence Relations

Similar Math Help Forum Discussions

Recurrence Relations

Recurrence relations

Recurrence relations

recurrence relations - degree of the recurrence

recurrence relations

Search Tags