going to examine them from an even more general point view, but here's an example.

So this is a second order of linear

occurrence with constant coefficients, like the Fibonacci numbers, and

so the idea is that it's hard to telescope this one.

You could try to telescope it, but very soon you have a lot of terms and

maybe not so much of an idea of where it's going to go so easily.

So one way to see how such an equation can be solved and again

this kind of a magic step, but I'll show next lecture how this becomes systematic.

Is to say well, I think that it's going to grow like some number to the Nth power.

So lets say that A N equals X to the N.

So if A N is going to be equal to X to the N, then it would have to be the case that

we have X to the N equals 5 X to the N minus 1 minus 6 X to the N minus 2.

In that kind of equation is a good thing for us,

because it means we can get rid of the N by just dividing X to the N minus 2.

For now we've just got a quadratic equation, and

we've known since middle school how to solve quadratic equations.

So that factors to x minus 2 times x minus 3.

And it means that both 2 to the n and

3 to the n are solutions to this, and actually

it's not too much of a step to see that the final solution must be of the form ace

of n equals some constant times 3 to the n plus some other constant times 2 to the n.

And again, I'm not going to go through the proof of these postulations,

because I'll give a very systematic way for doing it in just the next lecture.

But you can believe from these manipulations that that's what's gotta

happen, and so now what we have to do is find those two constants.

Well those two constants are easy to find, because the initial conditions.

We have two constants that we need, and

we have two initial conditions so we can just plug in for A0 and A1.

And it says that we must have that 0, which is A0, is equal to C0 plus C1.

And that one, which is A1 must be 3Z0 plus 2C1.

So those are simultaneously equations in c 0 and c 0, and

then the solution is c 0 equals 1 c 1 equals minus 1, 1 plus minus 1 is 0.

Three times 1 plus 2 times minus 1,

2 minus 2 is a 1 and then that's the solution.

Plus 3 to N minus 2 to the N is the solution to that equation,

and plug it in to check that's the answer, but

that definitely works in this case.

And that kind of technique is going to work for any second order

linear recurrence with constant coefficients, like the Fibonacci numbers.

Fibonacci numbers, the same setup, but the coefficients are both 1,

so then, we get xn = xn-1 = xn-2,

which gives us this quadratic equation, x2-x-1=0.

Solution to that, using the quadratic equation,

minus b plus/minus the square root of b squared minus 4 ac,

is going to have a square root of 5 in it, B squared is 1.

4 ac is minus 4.

Minus 4 ac is plus 4.

1 plus 4 is 5.

And so it works out from the quadratic equation.

That equation factors in terms of those two roots.

1 + the square root of 5 over 2, and 1- the square root of 5 over 2.

In this one, 1 + the square root of 5 over 2.

It's a very famous number known as the golden ration,

and maybe we'll come back to that at some time.

It has all kinds of interesting properties.

But in the current context, this just a root of that quadratic equation.