1. Start with an interview question

Every programmer has seen the following question from the time he first encountered a computer programming language to the time he worked as an engineer on a project:

  • There are many steps, you can take one step at a time, or you can take two steps at a time, so how many possibilities are there when you take steps?

There are many kinds of solutions, the most classic is the recursive solution, around the core idea of this solution is the famous Fibonacci sequence. (Although the recursive solution is a lot of calculation, but the algorithm optimization related content is not the scope of this paper).


2. Who is Fibonacci

Leonardo Fibonacci was an Italian mathematician whose main interests were geometry, trigonometry and the solution of equations of many variables. He published the Abacus in 1202. His handsome face is shown below:

3. Fibonacci numbers

What are Fibonacci numbers? Simply put, you have a sequence in which each term is the sum of the previous two terms. So the sequence starting from zero looks like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…


3.1 General term formula of Fibonacci sequence

If setIs the NTH term (n∈N*) of the sequence, then (please note that n is a positive integer, default range below) :


This doesn’t seem to be quite the same as what we remember about n-1 and n-2 solutions, because this is called the general term formula for a series of numbers. There are two formulas in the Fibonacci sequence, corresponding Chinese names are as follows:

  • Fibonacci general term formula

  • Fibonacci sequence expression








4. Basic knowledge of sequence

There are many kinds of sequences in mathematics, one of which is a recursive sequence, which means that each term in the sequence can be inferred from the other terms. Similar to the unary and binary definitions of equations, the recursive sequence also has a similar concept of “yuan”, called “order”. And the Fibonacci sequence is a second order recursive sequence. Let’s first take a look at the relevant definition of a recursive sequence:

Definition: Each item in a sequence determined by the functions of the preceding items is a predicate recursive sequence

General formula:, includingkIt’s called the order of a recursive sequence

When we set k=2, the above general formula becomes:

It conforms to the property that each term of the Fibonacci sequence is determined by the first two terms, and it follows that the Fibonacci sequence is a sufficient and unnecessary condition for the second order recursive sequence.


5. Derivation of general term formula of Fibonacci sequence

How to derive the general term formula of the sequence from the expression of the sequence? Before we do that, we can think back to our high school math class, how do we derive a function of two variables? The common method is to set:

Similarly, the general term formula for a sequence of numbers can be simplified as:

We just have to figure out what f(n) is. With that in mind, you can start exploring solutions.


Suppose there is (denoted as Equation 1) :


For the first deformation (denoted as Equation 2) :


We’re here, so what do we do next? You need flexible and divergent associations here, otherwise it’s really hard to move on. We observe that the parameters of the two equations on the right of the equal sign happen to be the general formula for the solution of the binary system of first order. So that:


And according to the relationship between quadratic roots and coefficients,andIt happens to be an equationThe solution. And because we know, the values of each subsequent term can be derived, so the values of A, b and c can be obtained by substituting them into Formula 1 (denoted as Formula 3) :


Formula 2 can be obtained:


We return to Equation 2 and perform the second transformation to obtain:


Open the parentheses and get the third deformation (denoted as Equation 3) :


Divide both sides of the equal sign, then:


And so we’re back in our high school math class, because we see that this is a geometric sequence:

It’s a geometric sequence, and the common ratio is zero


Similarly, in equation 3, if we takeMove to the left and you get:

It’s a geometric sequence, and the common ratio is zero


The general term formula is derived from geometric sequenceGet (denoted as Equation 4) :




Similarly (denoted as Equation 5) :


Subtract equations 4 and 5, and get:


Thus, we derive the general term formula of the sequence from the expression of the sequence:


Fibonacci series and golden ratio

Conclusion: The limit of the ratio of adjacent terms of Fibonacci sequence is 0.618. This means that as the Fibonacci sequence gets larger and larger, the ratio of adjacent terms gets closer and closer to 0.618. The proof is also very simple, as long as you have a knowledge of the limits of higher numbers in college:





If the limit exists, let’s say the limit is Q




7. Application of Fibonacci sequence

There are a large number of Fibonacci series cases in nature, and Fibonacci series has been widely used in industry, architecture and other aspects. I believe that everyone is familiar with it, and I will not repeat it in this paper. But it’s worth introducing an interesting toy called the Fibonacci Clock:

How do you calculate the current time? There are 5 square squares on the clock face with different sizes. The side lengths of each square correspond to Fibonacci sequence 1,1,2,3,5 respectively. They represent the value of hours or minutes.

Hours = Red + blue Minutes = (green + blue) x 5

I think this clock is full, but who needs to suffer, just think of waking up early and having to count the time in your head when you are sleepy-eyed. Hahaha ~


8. Expansion of the Fibonacci sequence

8.1 The Anti-Fibonacci sequence

The ratio of adjacent terms in the sequence is -0.618, which is the opposite of the ratio of adjacent terms in the Fibonacci sequence.


8.2 The Batuwan sequence

The expression for the Barduvan sequence is as follows:


What’s special about the Batuvan sequence? The Fibonacci sequence can be described as a square:

And the Batuwan sequence can be described as a triangle:

Math is wonderful


9. To summarize

Fibonacci sequence is the first and simplest mathematical logic for programmers. It can not only reason with basic high school mathematics knowledge, but also has a wealth of fun, which makes people can not help but admire the beauty of mathematics.