Learning Recurrence Relations: Challenges & Solutions

[SYoungblood]

Homework Statement

: [/B]
I am just learning recurrence relations, and they are proving challenging.

Homework Equations

-- [/B]Let's have x_n = 3x_n-1 + 6x_n-2.
I wanted to look at it with two scenarios. The first is x₀ = 1 and x₁ = 3. The second is x₁=3 and x₂ = 4

The Attempt at a Solution

Is there a difference between having a staring point of x₀and x₁? That is the sticking point.

As far as the solution is concerned, if I wanted to go to the 5th term, I can do the x₁=3 and x₂ = 4 scenario -- x₁ = 1, x₂ = 4, x₃ = x₃=30, x₄ = 114, and x₅= 522.

The scenario with x₀ is challenging to me. How can you have a recurrence relation where the n-1 term leaves you a negative number? How do you know where to start? Is it understood that, in the equation that is above, I would start with 3(x₀(or 3 * 1) + 6(x₁(6 * 3), with a sum of 21?

Also, how would you turn this into a formula? How do you determine the degree? For this last question, I just need a point in the right direction, I'm not asking for someone to do the questions for me.

 

[Ray Vickson]

Homework Statement

: [/B]
I am just learning recurrence relations, and they are proving challenging.

Homework Equations

-- [/B]Let's have x_n = 3x_n-1 + 6x_n-2.
I wanted to look at it with two scenarios. The first is x₀ = 1 and x₁ = 3. The second is x₁=3 and x₂ = 4

The Attempt at a Solution

Is there a difference between having a staring point of x₀and x₁? That is the sticking point.

As far as the solution is concerned, if I wanted to go to the 5th term, I can do the x₁=3 and x₂ = 4 scenario -- x₁ = 1, x₂ = 4, x₃ = x₃=30, x₄ = 114, and x₅= 522.

The scenario with x₀ is challenging to me. How can you have a recurrence relation where the n-1 term leaves you a negative number? How do you know where to start? Is it understood that, in the equation that is above, I would start with 3(x₀(or 3 * 1) + 6(x₁(6 * 3), with a sum of 21?

Also, how would you turn this into a formula? How do you determine the degree? For this last question, I just need a point in the right direction, I'm not asking for someone to do the questions for me.

The usual way of writing these things is as ##x_n = 3 x_{n-1} + 6x_{n-2} \; \text{for} \; \; n \geq 2##, with ##x_0=1, x_1 = 3##. In other words, the recursion does not apply when ##n = 0, 1##.

If you wanted a formula you could try ##x_n = r^n## for some ##r##. Then, the recursion would give ##r^n = 3 r^{n-1}+ 6 r^{n-2}##, or ##r^2 = 3 r + 6##. This is a quadratic, and so has two roots, usually---in this case it does have two real roots. So, the general solution would be of the form
[tex] x_n = A r_1^n + B r_2^n, \; n \geq 2 [/tex]
where ##r_1, r_2## are the two roots. We can find values of ##A, B## either by (i) requiring that this expression hold as well for ##n = 0,1##; or (ii) computing ##x_2, x_3## from the recursion as well as from the above formula, giviing two equations for ##A,B##.

 

[SYoungblood]

Thank you, this is something to speak about w/ the prof, it is still not sinking in.

 

[rcgldr]

In some cases, you can solve for negative n using the same recurrence relation. Given [itex]x_{n}[/itex] and [itex]x_{n-1}[/itex], you can solve for [itex]x_{n-2}[/itex]:
[tex]
x_n = 3x_{n-1} + 6x_{n-2} \\
x_{n-2} = (x_n - 3x_{n-1}) / 6 \\
x_1 = 3 \\
x_0 = 0 \\
x_{-1} = 1/2 \\
x_{-2} = -1/4 \\
x_{-3} = 5/24 \\
x_{-4} = -7/48 \\
x_{-5} = 31/288 \\
...
[/tex]