Fibonacci sequence

Example

The Fibonacci sequence $(F_n)_{n \ge 0}$ is the sequence of natural numbers defined by $$F_0 = 0, \qquad F_1 = 1, \qquad F_{n+2} = F_{n+1} + F_n.$$ It is an example of a sequence defined by a recurrence relation, and in particular of a linear recurrence with constant coefficients. Its first terms are $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$$

Remarks

The ratios $F_{n+1} / F_n$ tend to the golden ratio $\varphi = \frac{1 + \sqrt{5}}{2}$. Binet's formula gives $F_n$ in closed form. $F_{n+1}$ is the number of ways to tile a strip of length $n$ with squares of length $1$ and dominoes of length $2$.

Explanations

L1 human

Each Fibonacci number is the sum of the two before it: $5 + 8 = 13$, $8 + 13 = 21$, and so on. The numbers grow by a factor close to $1.618$ at each step.