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?