How to solve recurrence relation ???

[jjosephh]

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]

Hi jjosephh! Welcome to PF! :smile:

(try using the X2 and X2 tags just above the Reply box :wink:)
I could'nt do anything after find the roots ?

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 :smile:

[jjosephh]

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 :)

[CRGreathouse]

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

[jjosephh]

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

[tiny-tim]

Hi jjosephh! :wink:
a0 = 1 => K1 + K2 = 1
a1 = 3 => K1(-1-i) + K2(-1+i) = 3

Can you help me to find K1 and K2

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

[jjosephh]

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 ?
Thanks for all advices .

[tiny-tim]

In homog. solution i found r1 and r2 are both equal to 3.If roots are equal what should i do ?

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

[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! :smile:

[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,
an+2 - 6an+1 + 9an = 3*2n + 7*3n

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

[tiny-tim]

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

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

Hello again jjosephh! :smile:

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

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

[jjosephh]

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

[tiny-tim]

…what about the particular solution ?
should be f(n) = B12n + B23n
you mean ;
f(n) = B1(2n + 3n)
??

No … go back to B12n + B23n …

what did you get for B1 ?

[jjosephh]

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

[jjosephh]

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

[tiny-tim]

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

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

(and I get your B1, but not your B2)

[jjosephh]

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 :)

[tiny-tim]

he he :biggrin:

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 :smile: …

(and that should help you with the particular solution :wink:)

[jjosephh]

I could'nt calculate the particular solution
I said
F(n) = B1*2n + B2*3n
and after the equation

B1 = 3
But there is no B2..
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! :smile:

I get just 18D = 7

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