# Homework Help: Recurrence Relation to Non-recursive Formula

1. Jun 14, 2010

### pupeye11

1. The problem statement, all variables and given/known data

The sequence $$f_n$$ is defined by $$f_0=f_1=2$$ and

$$f_n = (\frac{f_{n-1}+2f_{n-2}}{6})$$, when $$n\geq2$$.

Find a non-recursive formula for $$f_n$$

3. The attempt at a solution

Well I have solved for the closed formula of the generating function which I will call g(x) so

$$g(x) = \frac{12-10x}{6-x-2x^2}$$

My question is, is this what they are looking for or do I need to continue and use partial fractions and linear algebra to get farther?

2. Jun 14, 2010

### Dick

They want to find a general formula for f_n. I think you want to find two solutions of the form (p1)^n and (p2)^n to your recursion relation and then combine them as c1*(p1)^n+c2*(p2)^n and solve for c1 and c2 to fit the initial conditions.

3. Jun 14, 2010

### pupeye11

Well I used Partial fractions and then linear algebra and got

$$c_1 = \frac{-6}{7}$$

$$c_2 = \frac{32}{7}$$

So where would I have to go from there

4. Jun 14, 2010

### Dick

I have no idea what you're doing unless you show what you are doing. I really don't think partial fractions or linear algebra have much to do with it. There are two exponential solutions to the linear recursion relation. I.e. of the form p^n. What are the p's? Use 'quadratic equation'.

5. Jun 14, 2010

### pupeye11

You lost me, what is the linear recursion relation (I am not huge on this terminology) That might also explain these p^n's you are talking about....

6. Jun 14, 2010

### Dick

Put f_n=p^n into the recurrence relation. You'll get a quadratic equation in p after you cancel some powers. Just try it. Since the equation in linear in f, linear combinations of those two solutions are also solutions. This is an awful lot like a linear second order ODE.

7. Jun 14, 2010

### pupeye11

The recurrence relation is the original formula I had? And if I put p^n in place of f_n the what would f_n-1 become?

8. Jun 14, 2010

### Dick

f_n-1 becomes p^(n-1) doesn't it?

9. Jun 14, 2010

### pupeye11

Ok so then my equation would be

$$6p^n -p^{n-1} - 2p^{n-2} = 0$$

so using the quadratic equation I get that

$$p = \frac{1 \pm \sqrt{27}}{12}$$

then what?

10. Jun 15, 2010

### Dick

Which quadratic did you solve to get those roots?? That's not what I get. Once you've got the correct roots, it's just what I said. Your solution is a linear combination of powers of the two roots. Solve for c1 and c2.

11. Jun 15, 2010

### pupeye11

If we put a p^n in for all f's we get

$$p^n = (\frac{p^{n-1}+2p^{n-2}}{6})$$

so multiplying both sides by six to get rid of the fraction and setting it equal to zero we get

$$6p^n -p^{n-1} - 2p^{n-2} = 0$$

which is the quadratic I solved. Unless a = -2, b=-1 and c=6. I did it the opposite way around where a=6, b=-1, and c=-2. Is that my mistake?

12. Jun 15, 2010

### Dick

b^2-4ac=1-(4*6*(-2))=49. There's no 'sqrt(27)' around. Even if you understand the problem perfectly, you'll never get the answer unless you take some care.

13. Jun 15, 2010

### pupeye11

I know, I was doing this really late at night but now I get that my roots are equal to

$$\frac{2}{3}, \frac{-1}{2}$$

I know you have said from there that they are a linear combination of powers of the two roots and I can solve it that way, but I do not know what a linear combination of powers is?

14. Jun 15, 2010

### Dick

(2/3)^n and (-1/2)^n solve your recurrence relation. So put f_n=c1*(2/3)^n+c2*(-1/2)^n. Solve for the constants c1 and c2.

15. Jun 15, 2010

### pupeye11

Ok, to solve for c1 and c2 though I would need two equations. Does that mean I need to use the fact that f_0=f_1=2 somehow?

16. Jun 15, 2010

### Dick

Yes.

17. Jun 15, 2010

### pupeye11

Oh, my two equations would be the following correct?

$$2=c_1\left(\frac{2}{3}\right)^0 + c_2\left(\frac{-1}{2}\right)^0$$

and

$$2=c_1\left(\frac{2}{3}\right)^1 + c_2\left(\frac{-1}{2}\right)^1$$

18. Jun 15, 2010

### Dick

Of course they would.

19. Jun 15, 2010

### pupeye11

So

$$c_1 = \frac{18}{7}$$

$$c_2 = \frac{-4}{7}$$

so what do those get put into to find the non-recursive formula for f_n ?

20. Jun 15, 2010

### Dick

A nonrecursive formula for f_n is a formula you can plug into your calculator to find f_n without first finding f_n-1 and f_n-2. What do we now have that might be such a formula?

21. Jun 15, 2010

### Hurkyl

Staff Emeritus
For the record, once he had the generating formula, he really could have used partial fractions and the geometric series formula to get the answer. (And no linear algebra involved)

22. Jun 15, 2010

### Dick

Thanks for pointing out there's another way. I just picked the method I knew.

23. Jun 15, 2010

### pupeye11

Would I need to put c_1 and c_2 back into

$$f_n=c_1\left(\frac{2}{3}\right)^n + c_2\left(\frac{-1}{2}\right)^n$$

Would that be the answer then?

24. Jun 15, 2010

### Dick

Of course. Check it. Find f_2 using the recursion relation and then find f_2 using that formula. Do they agree?

25. Jun 15, 2010

### pupeye11

They do indeed. Thanks for all your help :)