Recurrence Relation to Non-recursive Formula

[pupeye11]

Homework Statement

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

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?

 

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

 

[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

 

[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'.

 

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

 

[Dick]

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

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.

 

[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?

 

[Dick]

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?

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

 

[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?

 

[Dick]

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?

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.

 

[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?

 

[Dick]

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?

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.

 

[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?

 

[Dick]

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?

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

 

[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?

 

[Dick]

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?

Yes.

 

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

 

[Dick]

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

Of course they would.

 

[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 ?

 

[Dick]

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 ?

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?

 

[Hurkyl]

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)

 

[Dick]

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)

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

 

[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?

 

[Dick]

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?

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

 

[pupeye11]

They do indeed. Thanks for all your help :)