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
$$x_n = A r_1^n + B r_2^n, \; n \geq 2$$
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 $x_{n}$ and $x_{n-1}$, you can solve for $x_{n-2}$:
$$x_n = 3x_{n-1} + 6x_{n-2} \\<br /> x_{n-2} = (x_n - 3x_{n-1}) / 6 \\<br /> x_1 = 3 \\<br /> x_0 = 0 \\<br /> x_{-1} = 1/2 \\<br /> x_{-2} = -1/4 \\<br /> x_{-3} = 5/24 \\<br /> x_{-4} = -7/48 \\<br /> x_{-5} = 31/288 \\<br /> ...$$