# How to solve recurrence relation ?

1. May 8, 2010

### jjosephh

How to solve recurrence relation ???

The Example is ;

Solve the recurrence relation a n + 2a n-1 + 2a n-2 = 0 where n ≥ 2 and a 0 = 1 a 1 = 3
a n = nth order
a n-1 = (n-1)th order.
a n-2 = (n-2)th order.

I've started the solving ;
a n = r^n
so
the equation will be ;

r^n + 2r^(n-1) + 2r^(n-2)
r^2 + 2r + 2 = 0
I could'nt do anything after find the roots ?
What should i do ?
Thanks for helping.

2. May 8, 2010

### tiny-tim

Welcome to PF!

Hi jjosephh! Welcome to PF!

(try using the X2 and X2 tags just above the Reply box )
If your characteristic equation, r2 + 2r + 2 = 0, has roots p and q,

then the general soultion will be linear combinations of solutions to the equations

an = pan-1 and an = qan-1

3. May 8, 2010

### jjosephh

Re: How to solve recurrence relation ???

The problem is ;
Solve the recurrence relation a n + 2a(n-1) + 2a(n-2) = 0 where n ≥ 2 and a0 = 1 a 1 = 3

I said;

a n = rn

and found this equation ;

r2 + 2r +2 = 0

I have to find r1 and r2 to write ;

K1r12 + K2r22 = a n
I know a0 and a 1 so i can find K1 and K2

But i have problem with roots :)

4. May 8, 2010

### CRGreathouse

Re: How to solve recurrence relation ???

Use the quadratic formula. You'll have two complex roots (conjugates, naturally).

5. May 8, 2010

### jjosephh

Re: How to solve recurrence relation ???

I found

r1 = -1 -i
r2 = -1 +i

an = K1 r1n + K2 r2n

I'm trying to find K1 and K2

a0 = 1 => K1 + K2 = 1
a1 = 3 => K1(-1-i) + K2(-1+i) = 3

Can you help me to find K1 and K2

6. May 8, 2010

### tiny-tim

Hi jjosephh!
From the first equation, K2 = 1 - K1, so put that in the second equation, and that gives you an equation for K1.

7. May 8, 2010

### jjosephh

Re: How to solve recurrence relation ???

Thank you for all helps
I have another question ;
Solve the recurrence relation
an+2 - 6an+1 + 9an = 3*2n + 7*3n
where n>=0 and a0 = 1 a1 = 4

I think there are two path to solve this problem.
First path is find homogenous solution and the second is particular solution
So ;
In homog. solution i found r1 and r2 are both equal to 3.If roots are equal what should i do ? Or the roots are correct ?

8. May 8, 2010

### tiny-tim

The two independent solutions are an = 3n and an = n3n

9. May 8, 2010

### Gigasoft

Re: How to solve recurrence relation ???

When you have multiple roots, you must multiply the term with a polynomial. For double roots, the polynomial is n+1, and for triple roots, it's $$\frac{\left(n+1\right)\left(n+2\right)}2$$, etc.

We extend the definition of a to the negative domain, and let $$a_n=0$$ for $$n<0$$. Then we find the value of $$a_{n+2}-6a_{n+1}+9a_n$$ for $$n<0$$.

$$a_1-6a_0+9a_{-1}=-2$$
$$a_0-6a_{-1}+9a_{-2}=1$$
$$a_{n+2}-6a_{n+1}+9a_n=0$$ for $$n<-2$$.

Then the equation becomes:
$$a_{n+2}-6a_{n+1}+9a_n=H\left[n\right]\left(3\cdot 2^n+7\cdot 3^n\right)-2\delta\left[n+2\right]+\delta\left[n+1\right]$$, where H is the unit step function.

The Z-transform of this equation is:
$$A\left(z\right)=\frac{\frac 3{1-2z^{-1}}+\frac 7{1-3z^{-1}}-2z^2+z}{\left(z^2-6z+9\right)}=\frac{\frac 3{1-2z^{-1}}+\frac 7{1-3z^{-1}}-2z^2+z}{\left(z-3\right)^2}=\frac{3\left(1-3z^{-1}\right)+7\left(1-2z^{-1}\right)+\left(z-2z^2\right)\left(1-5z^{-1}+6z^{-2}\right)}{\left(1-2z^{-1}\right)\left(1-3z^{-1}\right)\left(z-3\right)^2}=$$
$$\frac{z^2-6z+1+17z^{-1}}{\left(1-2z^{-1}\right)\left(1-3z^{-1}\right)\left(z-3\right)^2}=$$
$$\frac{z^4-6z^3+z^2+17z}{\left(z-2\right)\left(z-3\right)^3}$$
We can write this as:
$$A\left(z\right)=\frac P{z-2}+\frac {Qz^2+Rz+S}{\left(z-3\right)^3}$$
Then:
$$P\left(z-3\right)^3+\left(Qz^2+Rz+S\right)\left(z-2\right)=P\left(z^3-9z^2+27z-27\right)+Q\left(z^3-2z^2\right)+R\left(z^2-2z\right)+S\left(z-2\right)=z^4-6z^3+z^2+17z$$
We can try solving it in this way:
$$P+Q=0$$
$$-9P-2Q+R=0$$
$$27P-2R+S=0$$
$$-27P-2S=z^4-6z^3+z^2+17z$$
This has the following solution:
$$P=-z^4+6z^3-z^2-17z$$
$$Q=z^4-6z^3+z^2+17z$$
$$R=-7z^4+42z^3-7z^2-119z$$
$$S=13z^4-78z^3+13z^2-221z$$
The inverse Z-transform of $$\frac{-z^4+6z^3-z^2-17z}{z-2}+\frac {13z^6-85z^5+56z^4+208z^3-118z^2+17z}{\left(z-3\right)^3}$$ is:
$$2^n\left(-8H\left[n+3\right]+24H\left[n+2\right]-2H\left[n+1\right]-17H\left[n\right]\right)+$$
$$\frac{3^n}2\left(351H\left[n+3\right]\left(n+4\right)\left(n+5\right)-765H\left[n+2\right]\left(n+3\right)\left(n+4\right)+168H\left[n+1\right]\left(n+2\right)\left(n+3\right)+$$
$$208H\left[n\right]\left(n+1\right)\left(n+2\right)-\frac{118}3H\left[n-1\right]\left n\left(n+1\right)+\frac{17}9H\left[n-2\right]\left(n-1\right)n\right)$$
So, that's your function, if my calculations are correct. If not, just follow this general method and you should get the correct answer. It can be simplified further by ignoring the H's and adding all the terms containing n.

10. May 9, 2010

### tiny-tim

(just got up :zzz: …)
Z-transform ??

jjosephh, ignore this very complicated method and just do it the way you were going to!

11. May 9, 2010

### Gigasoft

Re: How to solve recurrence relation ???

Yeah, I don't know if there's a simpler way to solve this, but remember that when you take into account the right hand side, the equation has four roots, three of which are 3 and one that is 2. So, the solution must have the form:
$$a_n=A2^n+(B+Cn+Dn^2)3^n$$

12. May 27, 2010

### jjosephh

Re: How to solve recurrence relation ???

Hello again,
an+2 - 6an+1 + 9an = 3*2n + 7*3n

what about the particular solution ?
should be f(n) = B12n + B23n

13. May 27, 2010

### tiny-tim

Hello again jjosephh!

I assume that you've got B1 but you've found the same method doesn't work for B2 ?

Start by trying the same trick that you're using for the ("= 0") general solution.

14. May 27, 2010

### jjosephh

Re: How to solve recurrence relation ???

you mean ;
f(n) = B1(2n + 3n)
??

15. May 27, 2010

### tiny-tim

No … go back to B12n + B23n

what did you get for B1 ?

16. May 27, 2010

### jjosephh

Re: How to solve recurrence relation ???

B1 = 3
B2 = -7/9
and the solution is ;
(I got before hom. solution A1= -11/9 A2 = 4/3)
an = -11/9*2n + 4/3*3n +3*2n -7/93n

17. May 27, 2010

### jjosephh

Re: How to solve recurrence relation ???

by the way a(0) = 1and a(1)=4
n>=2

18. May 27, 2010

### tiny-tim

I'm confused … how did you get that homogeneous solution from an+2 - 6an+1 + 9an ?

19. May 27, 2010

### jjosephh

Re: How to solve recurrence relation ???

r1,r2 = 3
so the solution must be
an+2 = rn
an+2 = A1*r1n + A2*n*r2n

an+2 = A1*31n + A2*n*32n

I think i need help :)

20. May 27, 2010

### tiny-tim

he he

No, if two roots of the characteristic equation are the same, you use Arn + Bnrn (three roots the same, + Cn2rn and so on …)

in this case, (A + Bn)3n