# 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