A Formula For Fibonacci Sequence

A Formula For Fibonacci Sequence

Image for postsource: https://pixabay.com

Fibonacci numbers are one of the most captivating things in mathematics. They hold a special place in almost every mathematician?s heart. Throughout history, people have done a lot of research around these numbers, and as a result, quite a lot of interesting facts have been discovered.

Let us see how they look like –

Image for post

Any number in this sequence is the sum of the previous two numbers, and this pattern is mathematically written as

Image for post

where n is a positive integer greater than 1, F? is the n?th Fibonacci number with F?=0 and F?=1.

Now, this expression is fairly easy to understand and quite sufficient to produce any Fibonacci number by plugging the required value of n. If at all, its only drawback is that, if we want to know a particular number, F?? in the sequence, we need two numbers F??? and F???? that came before it; that?s just how this formula works. It is not hard to imagine that if we need a number that is far ahead into the sequence, we will have to do a lot of ?back? calculations, which might be tedious.

In this article, we are going to discuss another formula to obtain any Fibonacci number in the sequence, which is (arguably) easier to work with.

The Formula

Let us define a function F(x), such that it can be expanded in a power series like this

Image for post

Here we have omitted F?, because F?=0, by definition.

(Issues regarding the convergence and uniqueness of the series are beyond the scope of the article)

Our job is to find an explicit form of the function, F(x), such that the coefficients, F?? are the Fibonacci numbers.

In order to make use of this function, first we have to rearrange the original formula. If we make the replacement

Image for post

the original formula becomes

Image for post

It is easy to check that this modification still produces the same sequence of numbers, starting from n=1, instead of n=0.

Next, we multiply the last equation by x? to get

Image for post

and perform a summation over n to get

Image for post

Let us first consider the left hand side of this equation ?

Image for post

Now, we try to represent this expansion in terms of F(x), by doing the following simple manipulations –

  • Multiply and divide by x to get

Image for post

  • Add and subtract x ? F?? to get

Image for post

Using the definition of F(x), this expression can now be written as

Image for post

Therefore, using the fact that F?=1, we can write the entire left hand side as

Image for post

Let us now consider the right hand side ?

Image for post

If we expand these two terms, we get

Image for post

We have again omitted F?, because F?=0.

By taking out a factor of x from the second expansion, we get

Image for post

Using the definition of F(x), this can finally be written as

Image for post

Therefore, by equating the left and the right hand sides, the original formula can be re-written in terms of F(x) as,

Image for post

Let us now simplify this expression a bit more. The denominator is a quadratic equation whose roots can easily be obtained to be

Image for post

(For an easy graphical method of finding roots, check out this article)

Using these roots, it is possible to write the denominator as

Image for post

so that we can write

Image for post

We can split the denominator and write this as

Image for post

Before we proceed, we need to understand a useful fact about geometric series. If we have an infinite series

Image for post

with |ax| < 1, then its sum is given by

Image for post

This means, if the sum of an infinite geometric series is finite, we can always have the following equality –

Image for post

Using this idea, we can write the expression of F(x) as

Image for post

The factor of 1/?5 is due to the substitution of ? and ?.

Recalling the original definition of F(x), we can finally write the following equality

Image for post

and by comparing the n?th terms on both sides, we get a nice result

Image for post

with

Image for post

(The number ? is also a very interesting object in itself. It goes by the name of golden ratio, which deserves its own separate article.)

We can see from the following table, that by plugging the values of n, we can directly find all Fibonacci numbers!

Image for post

This article was originally published at physicsgarage.

1

No Responses

Write a response