The Fibonacci Sequence

By Arun Iyer on Monday, July 09, 2001 - 07:03 pm:

Could you please give me the n^th term of a Fibonacci series.

P.S. For those who don't know this series it is,
0,1,1,2,3,5,8,13....
Every term is the sum of the two preceeding terms.

love arun

By Tom Hardcastle on Monday, July 09, 2001 - 07:25 pm:

The nth term of the fibonacci series is given by
(((1+5^1/2 )/2)ⁿ )/5^1/2 - (((1-5^1/2 )/2)ⁿ )/5^1/2 .

For a discussion of how to arrive at this and similar results see Difference Equations

By Olof Sisask on Monday, July 09, 2001 - 09:56 pm:

Do you know how to prove this Arun?

Olof

By Arun Iyer on Tuesday, July 10, 2001 - 12:18 pm:

Well Olof,

I read the section on difference equations. I don't know how to solve a second order linear differential equation

However, I just followed the steps given. That is, I found the roots p and q and put them in

y_n = Apⁿ + Bqⁿ

I then found the values of A and B by substituting the first two terms of the sequence into the formula and voila!

However, I don't know why this method works!
Could you tell me?

love arun

By Olof Sisask on Tuesday, July 10, 2001 - 01:51 pm:

Ah OK. You have

a_n+2 = a_n+1 + a_n
or
a_n+2 - a_n+1 - a_n = 0

for the Fibonacci sequence. Therefore consider

x² = x + 1
x² - x - 1 = 0

Let the roots of this equation be p and q, then

p² - p - 1 = 0
q² - q - 1 = 0

Subsituting a_n = Apⁿ + Bqⁿ into our difference equation:

LHS = Apⁿ⁺² + Bqⁿ⁺² - (Apⁿ⁺¹ + Bqⁿ⁺¹ ) - (Apⁿ + Bqⁿ ) = Apⁿ (p² - p - 1) + Bqⁿ (q² - q - 1) = Apⁿ *0 + Bqⁿ *0 = 0 = RHS.

Hope that's clear!

Regards,
Olof

By Arun Iyer on Tuesday, July 10, 2001 - 08:27 pm:

Thanks Olof.

However, I actually wanted to know why do we bring a quadratic equation into the frame? What is the reason behind this move?

love arun

By Olof Sisask on Tuesday, July 10, 2001 - 11:21 pm:

The quadratic is just a tool we use. If we assume that the solution to the difference equation is of the form y_n = Apⁿ + Bqⁿ , and we know of the recurrance relation y_n+2 + ay_n+1 + by_n = 0, then, upon substitution we end up with

LHS = Apⁿ⁺² + Bqⁿ⁺² + a(Apⁿ⁺¹ + Bqⁿ⁺¹ ) + b(Apⁿ + Bqⁿ )

Rearranging this:

LHS = Apⁿ (p² + ap + b) + Bqⁿ (q² + aq + b) (*)

For our original assumption to be correct, i.e. that the solution is of the form y_n = Apⁿ + Bqⁿ , then (*) must equal 0. Now, the only way to ensure this is to find values of p and q such that (p² + ap + b) and (q² + aq + b) both = 0. We therefore introduce the quadratic

x² + ax + b = 0

as a tool, as means to find such a p and such a q (as p and q will be the roots of this quadratic). That's really the only reason.

Regards,
Olof

By David Loeffler on Wednesday, July 11, 2001 - 12:59 am:

It is also possible to solve equations like this using matrices. This is a lot more laborious as one then has to do nasty things to the matrix; specifically, you have to find its eigenvalues and eigenvectors. However, it does give a somewhat clearer reason why quadratics come up: for a second-order difference equation like this one the matrix involved is 2x2, so its eigenvalues are the solutions of a quadratic polynomial.

This approach requires some rather heavy-duty tools but I think it makes it more obvious why all solutions should be obtainable by adding multiples of two powers.

By Michael Doré on Wednesday, July 11, 2001 - 11:47 am:

For another way of looking at essentially the same thing, note that if we have (for non-zero $b$ ):

$F_{n} + {aF}_{n - 1} + {bF}_{n - 2} = 0$

Then solving the equation $x^{2} + ax + b = 0$ you obtain two non-zero roots $λ_{1}$ and $λ_{2}$ such that:

$x^{2} + ax + b = (x - λ_{1}) (x - λ_{2})$

So $a = - (λ_{1} + λ_{2})$ , $b = λ_{1} λ_{2}$ .

The original recurrence then becomes:

$F_{n} - (λ_{1} + λ_{2}) F_{n - 1} + λ_{1} λ_{2} F_{n - 2} = 0$

Now make the substitution $G_{n} = F_{n} - λ_{1} F_{n - 1}$ . You immediately find:

$G_{n} - λ_{2} G_{n - 1} = 0$

In other words $G_{n} = G_{0} λ_{2}^{n}$ (by induction).

So:

$F_{n} - λ_{1} F_{n - 1} = G_{0} λ_{2}^{n}$

Divide through by $λ_{1}^{n}$ :

$F_{n} λ_{1}^{n} - F_{n - 1} / λ_{1}^{n - 1} = G_{0} (λ_{2} / λ_{1})^{n}$ So if you let $H_{n} = F_{n} / λ_{1}^{n}$ then:

$H_{n} - H_{n - 1} = G_{0} (λ_{2} / λ_{1})^{n}$

Add this equation to itself for successive values of $n$ , noting that (for distinct $λ_{1}$ and $λ_{2}$ ) the RHS becomes a geometric progression:

$H_{n} - H_{0} = G_{0} λ_{2} / λ_{1} ((λ_{2} / λ_{1})^{n} - 1) / (λ_{2} / λ_{1} - 1)$

If you now replace $H_{n}$ with $F_{n} / λ_{1}^{n}$ then you eventually obtain:

$F_{n} = P λ_{1}^{n} + Q λ_{2}^{n}$

for constants $P$ and $Q$ which is the desired result. A similar calculation may be performed for $λ_{1} = λ_{2}$ (you get an ` $n$ term' rather than the geometric progression). Of course this is more complicated than necessary but it shows how you can come up with the result without guessing a solution. This can be extended to higher order recurrences in a straightforward fashion.