How to solve recurrence relation ?

[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.

 

[tiny-tim]

Welcome to PF!

Hi jjosephh! Welcome to PF!

(try using the X² and X₂ tags just above the Reply box )

I could'nt do anything after find the roots ?

If your characteristic equation, r² + 2r + 2 = 0, has roots p and q,

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

a_n = pa_n-1 and a_n = qa_n-1

 

[jjosephh]

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

I said;

a _n = rⁿ

and found this equation ;

r² + 2r +2 = 0

I have to find r₁ and r₂ to write ;

K₁r₁² + K₂r₂² = a _n
I know a₀ and a ₁ so i can find K₁ and K₂

But i have problem with roots :)

 

[CRGreathouse]

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

 

[jjosephh]

I found

r₁ = -1 -i
r₂ = -1 +i

a_n = K₁ r₁ⁿ + K₂ r₂ⁿ

I'm trying to find K₁ and K₂

a₀ = 1 => K₁ + K₂ = 1
a₁ = 3 => K₁(-1-i) + K₂(-1+i) = 3

Can you help me to find K₁ and K₂

 

[tiny-tim]

Hi jjosephh!

a₀ = 1 => K₁ + K₂ = 1
a₁ = 3 => K₁(-1-i) + K₂(-1+i) = 3

Can you help me to find K₁ and K₂

From the first equation, K₂ = 1 - K₁, so put that in the second equation, and that gives you an equation for K₁.

 

[jjosephh]

Thank you for all helps
I have another question ;
Solve the recurrence relation
a_n+2 - 6a_n+1 + 9a_n = 3*2ⁿ + 7*3ⁿ
where n>=0 and a₀ = 1 a₁ = 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 r₁ and r₂ are both equal to 3.If roots are equal what should i do ? Or the roots are correct ?
Thanks for all advices .

 

[tiny-tim]

In homog. solution i found r₁ and r₂ are both equal to 3.If roots are equal what should i do ?

The two independent solutions are a_n = 3ⁿ and a_n = n3ⁿ

 

[Gigasoft]

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.

 

[tiny-tim]

(just got up :zzz: …)

The Z-transform of this equation is …

Z-transform ??

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

 

[Gigasoft]

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

 

[jjosephh]

Hello again,
a_n+2 - 6a_n+1 + 9a_n = 3*2ⁿ + 7*3ⁿ

what about the particular solution ?
should be f(n) = B₁2ⁿ + B₂3ⁿ

 

[tiny-tim]

Hello again,
a_n+2 - 6a_n+1 + 9a_n = 3*2ⁿ + 7*3ⁿ

what about the particular solution ?
should be f(n) = B₁2ⁿ + B₂3ⁿ

Hello again jjosephh!

I assume that you've got B₁ but you've found the same method doesn't work for B₂ ?

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

 

[jjosephh]

you mean ;
f(n) = B₁(2ⁿ + 3ⁿ)
??

 

[tiny-tim]

…what about the particular solution ?
should be f(n) = B₁2ⁿ + B₂3ⁿ

you mean ;
f(n) = B₁(2ⁿ + 3ⁿ)
??

No … go back to B₁2ⁿ + B₂3ⁿ …

what did you get for B₁ ?

 

[jjosephh]

B₁ = 3
B₂ = -7/9
and the solution is ;
(I got before hom. solution A₁= -11/9 A₂ = 4/3)
a_n = -11/9*2ⁿ + 4/3*3ⁿ +3*2ⁿ -7/93ⁿ

 

[jjosephh]

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

 

[tiny-tim]

(I got before hom. solution A₁= -11/9 A₂ = 4/3)
a_n = -11/9*2ⁿ + 4/3*3ⁿ +3*2ⁿ -7/93ⁿ

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

(and I get your B₁, but not your B₂)

 

[jjosephh]

r₁,r₂ = 3
so the solution must be
a_n+2 = rⁿ
a_n+2 = A₁*r₁ⁿ + A₂*n*r₂ⁿ

a_n+2 = A₁*3₁ⁿ + A₂*n*3₂ⁿ

I think i need help :)

 

[tiny-tim]

he he

No, if two roots of the characteristic equation are the same, you use Arⁿ + Bnrⁿ (three roots the same, + Cn²rⁿ and so on …)

in this case, (A + Bn)3ⁿ …

(and that should help you with the particular solution )

 

[jjosephh]

I could'nt calculate the particular solution
I said
F(n) = B₁*2ⁿ + B₂*3ⁿ
and after the equation

B₁ = 3
But there is no B₂..
what should be f(n) ?
could you help me please ..

 

[jjosephh]

if
f(n) = A*2^n + (B+Cn+Dn^2)*3^n
A = 3
18D + 9Cn = 7
so what can i do ... ??

 

[tiny-tim]

if
f(n) = A*2^n + (B+Cn+Dn^2)*3^n
A = 3
18D + 9Cn = 7
so what can i do ... ??

Hi jjosephh!

I get just 18D = 7

(but 18D + 9Cn = 7 would mean that 9C = 0, since it has to be true for any n )