Homework Help: Recurrence relations

Tags:
1. Apr 1, 2015

SYoungblood

1. The problem statement, all variables and given/known data:
I am just learning recurrence relations, and they are proving challenging.

2. Relevant equations -- Let's have xn = 3xn-1 + 6xn-2.
I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4

3. The attempt at a solution
Is there a difference between having a staring point of x0and x1? 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 x1=3 and x2 = 4 scenario -- x1 = 1, x2 = 4, x3 = x3=30, x4 = 114, and x5= 522.

The scenario with x0 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(x0(or 3 * 1) + 6(x1(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.

2. Apr 1, 2015

Ray Vickson

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

3. Apr 1, 2015

SYoungblood

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

4. Apr 1, 2015

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} \\ 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 \\ ...$$

Last edited: Apr 2, 2015