Data Modelling & AI Data Structure & Algorithm

Deriving the expression of Fibonacci Numbers in terms of golden ratio

23 June 2025

0

Prerequisites: Generating Functions, Fibonacci Numbers, Methods to find Fibonacci numbers.

The method of using Generating Functions to solve the famous and useful Fibonacci Numbers‘ recurrence has been discussed in this post.

The Generating Function is a powerful tool for solving a wide variety of mathematical problems, including counting problems. It is a formal power series. For example, in counting problems, we are often interested in finding the number of objects of size $n$ . In such a case, we define a power series, which, in simple terms is an infinite term polynomial where the coefficient of the $nth$ degree term is the $nth$ term of the sequence. This helps us to find many interesting and important results. It should be noted that in the use of generating functions, we generally use the coefficients in the generating function power series, we rarely use the variable in the series. In this post too, we shall do the same. The ordinary generating function of some a_n is:

$\mathcal{G}(a_{n};x) = \sum_{n=0}^{\infty}a_{n}x^n$

Fibonacci Numbers are one of the fundamental sequences in mathematics, and numerous ways have been discovered to find out the higher order terms of this sequence. This post discusses one such method.

Let’s first define a generating function for the Fibonacci Numbers, and then the function will be simplified to get a recurrence. Using this, expand the simplification and break it into partial fractions, and then use two standard power series, and later combine them both to arrive at surprising result for the $ith$ term of the Fibonacci Series.

Let us define the generating function $\mathcal{F}$ as

$\mathcal{F}(z) = \sum_{i=0}^{\infty}F_{i}z^i$

$\mathcal{F}(z) = 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + ... \infty$ ,

where $F_{i}$ is the ith Fibonacci Number.

Since,

$\mathcal{F}(z) = z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + ... \infty$ .

$\mathcal{F}(z) = z + (1 + 0)z^2 + (1 + 1)z^3 + (2 + 1)z^4 + (3 + 2)z^5 + (5 + 3)z^6 + ... \infty$ .

Rearranging them we get,

$\mathcal{F}(z) = z + [z^2 + z^3 + 2z^4 + 3z^5 + 5z^6 + ... \infty] + [0 + z^3 + z^4 + 2z^5 + 3z^6 + ... \infty]$ .

Taking the common terms,

$\mathcal{F}(z) = z + (z)[z + z^2 + 2z^3 + 3z^4 + 5z^5 + ... \infty]$
$+ (z^2)[0 + z^1 + z^2 + z^3 + 3z^4 + ... \infty]$

Simplifying it further, the below function is obtained.

$\mathcal{F}(z) = z + z\mathcal{F}(z) + z^2\mathcal{F}(z)$ .

Solving for $\mathcal{F}(z)$ , we get:

$\mathcal{F}(z) = \frac{z}{1-z-z^2}$ .

We get the below formula by above operations:

$1-z-z^2 = -(z + \phi)(z + \widehat{\phi})$ ,

where, $\phi = \frac{1+\sqrt{5}}{2}$ and $\widehat{\phi} = \frac{1-\sqrt{5}}{2}$ .

Thus,

$\mathcal{F}(z) = \frac{-z}{(z + \phi)(z + \widehat{\phi})}$
Also note that,

$\phi\widehat{\phi} = -1$ .

Thus, keeping this relation in above expression, we get,

$\mathcal{F}(z) = \frac{z}{(1-z\phi)(1 - z\widehat{\phi})}$ .

Now the right hand side of the above expression can be separated into partial fractions,

$\mathcal{F}(z) = \frac{1}{\sqrt{5}}\left [ \frac{1}{(1-\phi z)} - \frac{1}{(1-\widehat{\phi} z)}\right ]$ .

Using Expansion on the two fractions,

$\frac{1}{(1-\phi z)} = 1 + \phi z + \phi ^2 z^2 + \phi ^3 z^3 + ... \infty = \sum_{i=0}^{\infty}\phi ^iz^i$ .

Similarly,

$\frac{1}{(1-\widehat{\phi} z)} = 1 + \widehat{\phi} z + \widehat{\phi} ^2 z^2 + \widehat{\phi} ^3 z^3 + ... \infty = \sum_{i=0}^{\infty}\widehat{\phi} ^iz^i$ .

Thus,

$\mathcal{F}(z) = \sum_{i=0}^{\infty}\frac{1}{\sqrt{5}}(\phi ^iz^i - \widehat{\phi} ^iz^i)$ .

Thus,

$F_{i} = \frac{1}{\sqrt{5}}(\phi ^i - \widehat{\phi} ^i)$ .

Now,

$\left | \phi \right | < 1$ ,

and,

$\left | \frac{\widehat{\phi} ^i}{\sqrt{5}} \right | < \left | \frac{\phi ^i}{\sqrt{5}} \right | < \frac{1}{2}$

Using the above two facts, it can be safely concluded that the value of

$F_{i} = \frac{\phi ^i}{\sqrt{5}}$ , rounded to the nearest integer.

Finding n-th Fibonacci number using Golden ratio is one of the applications of this formula.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Deriving the expression of Fibonacci Numbers in terms of golden ratio

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

I asked NotebookLM to make sense of my digital chaos — and it kind of did

They just made zoom in and enhance REAL. [Video]

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

Pixel Tablet’s biggest weakness isn’t performance — it’s its USB port

EDITOR PICKS

I asked NotebookLM to make sense of my digital chaos — and it kind of did

They just made zoom in and enhance REAL. [Video]

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

POPULAR POSTS

I asked NotebookLM to make sense of my digital chaos — and it kind of did

They just made zoom in and enhance REAL. [Video]

Is the Oura Ring 4 Ceramic worth buying? I’ve worn it to find out

POPULAR CATEGORY

ABOUT US

FOLLOW US