A Formula For Fibonacci Sequence


5 min read
A Formula For Fibonacci Sequence

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 -

$$0, 1, 1, 2, 3, 5, 8, 13 ,21, 34, 55, \cdots$$

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

$$F_n = F_{n-1} + F_{n-2},$$

where $n$ is a positive integer greater than $1$, $F_n$ is the $n-$th Fibonacci number with $F_0 = 0$ and $F_1=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_n$ in the sequence, we need two numbers $F_{n-1}$ and $F_{n-2}$ 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 might (arguably) be 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

$$F(x) = \sum_{n \ge 0}x^n F_n = x \cdot F_1 + x^2 \cdot F_2 + \cdots$$

Here we have omitted $F_0$, because $F_0=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_n$ 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

$$n \to n+1,$$

the original formula becomes

$$F_{n+1} = F_n + F_{n-1}$$

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_n$ to get

$$x^n \cdot F_{n+1} = x^n \cdot F_n + x^n \cdot F_{n-1},$$

and perform a summation over $n$ to get

$$\sum_{n \ge 1}x^n \cdot F_{n+1} = \sum_{n \ge 1} x^n \cdot F_n + \sum_{n \ge 1} x^n \cdot F_{n-1}$$

Let us first consider the left hand side -

$$\sum_{n \ge 1} x^n \cdot F_{n+1} = x \cdot F_2 + x^2 \cdot F_3 + \cdots $$

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

$$\frac{1}{x} \left( x^2 \cdot F_2 + x^3 \cdot F_3 + \cdots \right)$$

  • Add and subtract $x \cdot F_1$ to get

$$\frac{1}{x} \left(- x \cdot F_1 + x \cdot F_1 + x^2 \cdot F_2 + x^3 \cdot F_3 + \cdots \right)$$

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

$$\frac{1}{x} \left(- x \cdot F_1 + F(x)\right)$$

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

$$\sum_{n \ge 1} x^n \cdot F_{n+1} = x \cdot F_2 + x^2 \cdot F_3 + \cdots = \frac{F(x) - x}{x}$$

Let us now consider the right hand side,

$$\sum_{n \ge 1}x^n \cdot F_n + \sum_{n \ge 1} x^n \cdot F_{n-1}.$$

If we expand these two terms, we get

$$\left( x \cdot F_1 + x^2 \cdot F_2 + \cdots \right ) + \left( x^2 \cdot F_1 + x^3 \cdot F_2 + \cdots \right)$$

We have again omitted $F_0$, because $F_0=0$.

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

$$\left( x \cdot F_1 + x^2 \cdot F_2 + \cdots \right ) + x \left( x \cdot F_1 + x^2 \cdot F_2 + \cdots \right).$$

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

$$F(x) + x F(x).$$

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

$$\frac{F(x) - x}{x} = F(x) + xF(x) ~~ \Longrightarrow ~~ F(x) = \frac{x}{1-x-x^2}$$

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

$$\alpha = \frac{1 + \sqrt{5}}{2}, ~~~ \beta = \frac{1 - \sqrt{5}}{2}.$$

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

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

$$1-x-x^2 = (1-x\alpha)(1-x\beta),$$

so that we can write

$$F(x) = \frac{x}{1-x-x^2} = \frac{x}{(1-x\alpha)(1-x\beta)}$$

We can further write this as

$$F(x) = \frac{x}{(1-x\alpha)(1-x\beta)} = \frac{1}{(\alpha - \beta)}\left(\frac{1}{1-x\alpha} - \frac{1}{1-x\beta} \right)$$

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

$$S = 1 + ax + (ax)^2 + (ax)^3 + \cdots, $$

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

$$S = \frac{1}{1 - ax}$$

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

$$\frac{1}{1 - ax} = 1 + ax + (ax)^2 + (ax)^3 + \cdots = \sum_{n \ge 0} a^n x^n$$

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

$$F(x) = \frac{1}{(\alpha - \beta)}\left(\frac{1}{1-x\alpha} - \frac{1}{1-x\beta} \right) = \frac{1}{\sqrt{5}} \left(\sum_{n \ge 0 } x^n\alpha^n - \sum_{n \ge 0 } x^n \beta^n \right)$$

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

$$F(x) = \sum_{n \ge 0}F_n x^n = \frac{1}{\sqrt{5}} \left(\sum_{n \ge 0 } x^n\alpha^n - \sum_{n \ge 0 } x^n \beta^n \right),$$

and comparing the $n-$th terms on both sides, we get a nice result

$$F_n = \frac{1}{\sqrt{5}} \left(\alpha^n - \beta^n \right),$$

with

$$\alpha = \frac{1 + \sqrt{5}}{2}, ~~~ \beta = \frac{1 - \sqrt{5}}{2}.$$

(This number $\alpha$ is also a very interesting number 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!

Subscribe to the newsletter to receive more stories mailed directly to your inbox

Related Articles

A Derivation of Euler's Formula
4 min read
Mighty Ruler Conquers Quadratic Equations
6 min read
A clever formula for Logarithm
2 min read

GO TOP

🎉 You've successfully subscribed to Physics Garage!
OK