How to solve recurrence relation ?

In summary: B2n = C2n + D2n^2but remember that n=0 and n=1 give you two equations for B2 and B3.So you have to solve:B2n = C2n + D2n^2B2 = C2 + D2B3 = C3 + D6and that's easy, isn't it? :)In summary, to solve a recurrence relation, you can use the method of finding a general homogeneous solution and a particular solution. To find the general homogeneous solution, you can use the characteristic equation and find the roots, taking into account the order of the equation. For multiple roots, you must multiply the term with
  • #1
jjosephh
11
0
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.
 
Mathematics news on Phys.org
  • #2
Welcome to PF!

Hi jjosephh! Welcome to PF! :smile:

(try using the X2 and X2 tags just above the Reply box :wink:)
jjosephh said:
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:
 
  • #3


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


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


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
Hi jjosephh! :wink:
jjosephh said:
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:
 
  • #7


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 .
 
  • #8
jjosephh said:
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:
 
  • #9


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 [tex]\frac{\left(n+1\right)\left(n+2\right)}2[/tex], etc.

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

[tex]a_1-6a_0+9a_{-1}=-2[/tex]
[tex]a_0-6a_{-1}+9a_{-2}=1[/tex]
[tex]a_{n+2}-6a_{n+1}+9a_n=0[/tex] for [tex]n<-2[/tex].

Then the equation becomes:
[tex]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][/tex], where H is the unit step function.

The Z-transform of this equation is:
[tex]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}=[/tex]
[tex]\frac{z^2-6z+1+17z^{-1}}{\left(1-2z^{-1}\right)\left(1-3z^{-1}\right)\left(z-3\right)^2}=[/tex]
[tex]\frac{z^4-6z^3+z^2+17z}{\left(z-2\right)\left(z-3\right)^3}[/tex]
We can write this as:
[tex]A\left(z\right)=\frac P{z-2}+\frac {Qz^2+Rz+S}{\left(z-3\right)^3}[/tex]
Then:
[tex]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[/tex]
We can try solving it in this way:
[tex]P+Q=0[/tex]
[tex]-9P-2Q+R=0[/tex]
[tex]27P-2R+S=0[/tex]
[tex]-27P-2S=z^4-6z^3+z^2+17z[/tex]
This has the following solution:
[tex]P=-z^4+6z^3-z^2-17z[/tex]
[tex]Q=z^4-6z^3+z^2+17z[/tex]
[tex]R=-7z^4+42z^3-7z^2-119z[/tex]
[tex]S=13z^4-78z^3+13z^2-221z[/tex]
The inverse Z-transform of [tex]\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}[/tex] is:
[tex]2^n\left(-8H\left[n+3\right]+24H\left[n+2\right]-2H\left[n+1\right]-17H\left[n\right]\right)+[/tex]
[tex]\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)+[/tex]
[tex]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)[/tex]
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
(just got up :zzz: …)
Gigasoft said:
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:
 
  • #11


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:
[tex]a_n=A2^n+(B+Cn+Dn^2)3^n[/tex]
 
  • #12


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

what about the particular solution ?
should be f(n) = B12n + B23n
 
  • #13
jjosephh said:
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:
 
  • #14


you mean ;
f(n) = B1(2n + 3n)
??
 
  • #15
jjosephh said:
…what about the particular solution ?
should be f(n) = B12n + B23n
jjosephh said:
you mean ;
f(n) = B1(2n + 3n)
??

No … go back to B12n + B23n

what did you get for B1 ?
 
  • #16


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


by the way a(0) = 1and a(1)=4
n>=2
 
  • #18
jjosephh said:
(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)
 
  • #19


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
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:)
 
  • #21


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 ..
 
Last edited:
  • #22


if
f(n) = A*2^n + (B+Cn+Dn^2)*3^n
A = 3
18D + 9Cn = 7
so what can i do ... ??
 
  • #23
jjosephh said:
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:)
 

What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of values, where each value is determined by previous values in the sequence.

Why do we need to solve recurrence relations?

Solving recurrence relations allows us to find a general formula for the sequence, which can help us predict future terms and understand the behavior of the sequence.

How do I solve a recurrence relation?

There are several methods for solving recurrence relations, including substitution, iteration, and generating functions. The best method will depend on the specific type of recurrence relation.

What is the difference between homogeneous and non-homogeneous recurrence relations?

A homogeneous recurrence relation has a constant coefficient for each term, while a non-homogeneous recurrence relation has a variable coefficient. Solving a homogeneous recurrence relation is typically easier than solving a non-homogeneous one.

Can recurrence relations be used in real-world applications?

Yes, recurrence relations can be used to model various real-world situations, such as population growth, stock prices, and algorithms. They can also be used in computer science for analyzing the time complexity of algorithms.

Similar threads

  • General Math
Replies
12
Views
2K
  • General Math
Replies
1
Views
825
  • General Math
Replies
1
Views
1K
Replies
3
Views
982
  • General Math
Replies
11
Views
1K
Replies
13
Views
1K
  • General Math
Replies
4
Views
2K
Replies
3
Views
1K
Replies
12
Views
900
  • General Math
Replies
4
Views
1K
Back
Top