The Fibonacci sequence is the list of numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, … in which every number is the sum of the two numbers before it. Its terms are called Fibonacci numbers. You only need the first two numbers and the rule “add the last two,” and you can continue the list as far as you like. People also say Fibonacci series, pattern or progression, but in mathematics the right word is sequence.
The sequence is named after Leonardo of Pisa, nicknamed Fibonacci, who used it in 1202 to solve a rabbit problem in his book Liber abaci. On this page you build the sequence yourself, work with the recursive formula and Binet’s formula, see the first 50 numbers, connect it to the golden ratio and Pascal’s triangle, and check which claims about nature are true. At the end you find code in Python, a note on agile story points and exercises with answers. Who Leonardo was is told on the Fibonacci biography (in German).
What is the Fibonacci sequence? The rule and the first terms
Write down two 1s. The third number is their sum: 1 + 1 = 2. The fourth is the sum of the second and third: 1 + 2 = 3. Then follow 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13 and so on. Each step uses only the two newest numbers.
Many books start one step earlier, with F0 = 0 (so the list reads 0, 1, 1, 2, 3, 5, …). From F1 on, both versions are identical. The sequence does not stop at 100, so it has no “last” Fibonacci number. The first 20 are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1,597, 2,584, 4,181 and 6,765.
List of the first 50 Fibonacci numbers
All Fibonacci numbers below 1,000 are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 and 987. The next one, 1,597, is already larger. The table lists the first 50 numbers.
| n | Fn | n | Fn |
|---|---|---|---|
| 1 | 1 | 26 | 121,393 |
| 2 | 1 | 27 | 196,418 |
| 3 | 2 | 28 | 317,811 |
| 4 | 3 | 29 | 514,229 |
| 5 | 5 | 30 | 832,040 |
| 6 | 8 | 31 | 1,346,269 |
| 7 | 13 | 32 | 2,178,309 |
| 8 | 21 | 33 | 3,524,578 |
| 9 | 34 | 34 | 5,702,887 |
| 10 | 55 | 35 | 9,227,465 |
| 11 | 89 | 36 | 14,930,352 |
| 12 | 144 | 37 | 24,157,817 |
| 13 | 233 | 38 | 39,088,169 |
| 14 | 377 | 39 | 63,245,986 |
| 15 | 610 | 40 | 102,334,155 |
| 16 | 987 | 41 | 165,580,141 |
| 17 | 1,597 | 42 | 267,914,296 |
| 18 | 2,584 | 43 | 433,494,437 |
| 19 | 4,181 | 44 | 701,408,733 |
| 20 | 6,765 | 45 | 1,134,903,170 |
| 21 | 10,946 | 46 | 1,836,311,903 |
| 22 | 17,711 | 47 | 2,971,215,073 |
| 23 | 28,657 | 48 | 4,807,526,976 |
| 24 | 46,368 | 49 | 7,778,742,049 |
| 25 | 75,025 | 50 | 12,586,269,025 |
The numbers grow fast. F100 already has 21 digits: 354,224,848,179,261,915,075. Every five steps a Fibonacci number becomes about 11 times as large (φ5 ≈ 11.09), so roughly one digit is added per five terms. A complete list of the first 100 or 500 numbers is better produced by a short program, like the one below.
The rabbit problem from the Liber abaci
In Europe the sequence appears for the first time in Leonardo’s arithmetic book Liber abaci of 1202, a textbook for merchants. He asks, in effect: a man keeps one pair of rabbits in an enclosed garden. How many pairs are there after one year, if every pair has one new pair each month, and the new pairs start having young themselves in their second month?
We assume the first pair is adult and that no rabbit dies. A newborn pair is too young to breed in the following month and has its first pair of young one month after that.
| Month | Pairs at the start | Newborn pairs | Pairs at the end |
|---|---|---|---|
| Start | 1 | 0 | 1 |
| 1 | 1 | 1 | 2 |
| 2 | 2 | 1 | 3 |
| 3 | 3 | 2 | 5 |
| 4 | 5 | 3 | 8 |
| 5 | 8 | 5 | 13 |
| 6 | 13 | 8 | 21 |
| 7 | 21 | 13 | 34 |
| 8 | 34 | 21 | 55 |
| 9 | 55 | 34 | 89 |
| 10 | 89 | 55 | 144 |
| 11 | 144 | 89 | 233 |
| 12 | 233 | 144 | 377 |
After twelve months there are 377 pairs, counting the first pair. The number of newborn pairs equals the number of adult pairs, which is the total from two months earlier. So the total is always the sum of the two previous months. After t months there are Ft+2 pairs, which makes 377 equal to F14, not F12. The sequence was not discovered by Leonardo alone: Indian scholars of poetry had counted the same numbers centuries earlier.
Who was Fibonacci?
Leonardo of Pisa, also called Leonardo Pisano or Fibonacci, was born around 1170, probably in Pisa. His father represented Pisan merchants at the customs house in Bugia (today Béjaïa in Algeria), so Leonardo learned mathematics in North Africa and traveled widely. Around 1200 he returned to Pisa. His Liber abaci (“Book of Calculation,” 1202, revised 1228) taught merchants the Indian digits and how to use them for trade. His other works include the Practica geometriae (1220) and the Liber quadratorum (1225). Little else is known about his life. More about the digits themselves is on the page Hindu-Arabic numerals.
Fibonacci formula: recursive and explicit
The recursive formula
The recursive formula is the rule above: Fn = Fn−1 + Fn−2 with F1 = F2 = 1. Its drawback is that you must compute all earlier terms before you reach F40. Example: F15 = F14 + F13 = 377 + 233 = 610.
The explicit formula (Binet’s formula)
An explicit formula gives Fn straight from n. For the Fibonacci numbers it is named after Jacques Binet, who published it in 1843, although Abraham de Moivre and Daniel Bernoulli knew it a century earlier.
For larger n the term ψn becomes tiny, because ψ is smaller than 1 in absolute value. So Fn is simply the whole number closest to φn / √5. For n = 15 you get φ15 / √5 ≈ 609.9997, which rounds to 610 = F15.
Where does the formula come from? (advanced)
- Look for sequences qn that obey the rule qn = qn−1 + qn−2. Divide by qn−2 and you are left with q2 = q + 1.
- This quadratic equation has the solutions q = (1 ± √5) / 2, which are φ and ψ.
- Every mixture a · φn + b · ψn obeys the rule as well.
- Fit a and b to F0 = 0 and F1 = 1: from a + b = 0 and a · φ + b · ψ = 1 follows a = 1 / √5 and b = −1 / √5.
Fibonacci numbers and the golden ratio
Divide each Fibonacci number by the one before it. The quotients jump back and forth at first, then settle down on one number.
| n | Fn+1 : Fn | Ratio | Compared with φ |
|---|---|---|---|
| 1 | 1 : 1 | 1.000000 | below |
| 2 | 2 : 1 | 2.000000 | above |
| 3 | 3 : 2 | 1.500000 | below |
| 4 | 5 : 3 | 1.666667 | above |
| 5 | 8 : 5 | 1.600000 | below |
| 6 | 13 : 8 | 1.625000 | above |
| 7 | 21 : 13 | 1.615385 | below |
| 8 | 34 : 21 | 1.619048 | above |
| 9 | 55 : 34 | 1.617647 | below |
| 10 | 89 : 55 | 1.618182 | above |
| 11 | 144 : 89 | 1.617978 | below |
| 12 | 233 : 144 | 1.618056 | above |
They swing above and below φ ≈ 1.618034, the number of the golden ratio. You can see why in one line: if q = Fn+1 / Fn approaches a fixed value, the rule Fn+1 = Fn + Fn−1 turns into q = 1 + 1 / q, that is q2 = q + 1. Its positive solution is φ, so this equation is the “Fibonacci equation.” Johannes Kepler noticed the connection in 1611. For the claims that go beyond this, read the German article The golden ratio: what is true and what is myth, and for your own calculations the golden ratio calculator (interface in German).
Some simple properties
Every third Fibonacci number is even
Odd plus odd is even, and odd plus even is odd. The sequence starts odd, odd, so the pattern is odd, odd, even, odd, odd, even, and so on. F3, F6, F9, … are even, for example F12 = 144 and F30 = 832,040.
The sum of the first n terms
For n = 10: 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143, and F12 − 1 = 144 − 1 = 143. The reason: the rule gives Fk = Fk+2 − Fk+1. Write every term that way and almost everything cancels, leaving Fn+2 − F2 = Fn+2 − 1.
The greatest common divisor
For the greatest common divisor (gcd) the rule is gcd(Fm, Fn) = Fgcd(m, n). Example: gcd(12, 18) = 6, so gcd(F12, F18) = F6 = 8. Check: 144 = 8 · 18 and F18 = 2,584 = 8 · 323. Because gcd(n, n + 1) = 1 and F1 = 1, neighboring Fibonacci numbers never share a divisor.
Every number is a sum of Fibonacci numbers
Each positive whole number can be written as a sum of Fibonacci numbers, and if you never use two neighbors, the sum is unique. This is Zeckendorf’s theorem. Examples: 50 = 34 + 13 + 3 and 100 = 89 + 8 + 3. Marking the numbers you use with 1 and the others with 0 gives the “Fibonacci code,” a way to write numbers that is used in data compression.
Related sequences: the Lucas numbers
Start with 2 and 1 instead of 1 and 1 and keep adding the last two numbers, and you get the Lucas numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, … Every Lucas number is the sum of the two Fibonacci numbers around it, for example 11 = 3 + 8. Any other pair of starting values gives a “Fibonacci-like” sequence; 2, 5, 7, 12, 19, 31, … is one.
Fibonacci numbers in Pascal’s triangle
In Pascal’s triangle every number is the sum of the two above it. Add the numbers along the shallow diagonals and the sums are exactly the Fibonacci numbers. The triangle is named after Blaise Pascal (in German), but Chinese and Persian mathematicians knew it long before him.
| Row | Numbers in the row |
|---|---|
| 0 | 1 |
| 1 | 1 1 |
| 2 | 1 2 1 |
| 3 | 1 3 3 1 |
| 4 | 1 4 6 4 1 |
| 5 | 1 5 10 10 5 1 |
| 6 | 1 6 15 20 15 6 1 |
| 7 | 1 7 21 35 35 21 7 1 |
| 8 | 1 8 28 56 70 56 28 8 1 |
| Diagonal | Numbers added | Sum | Fibonacci number |
|---|---|---|---|
| 0 | 1 | 1 | F1 |
| 1 | 1 | 1 | F2 |
| 2 | 1 + 1 | 2 | F3 |
| 3 | 1 + 2 | 3 | F4 |
| 4 | 1 + 3 + 1 | 5 | F5 |
| 5 | 1 + 4 + 3 | 8 | F6 |
| 6 | 1 + 5 + 6 + 1 | 13 | F7 |
| 7 | 1 + 6 + 10 + 4 | 21 | F8 |
| 8 | 1 + 7 + 15 + 10 + 1 | 34 | F9 |
Take diagonal 6: starting in row 6 and moving one row up and one place right each time, you add 1 + 5 + 6 + 1 = 13 = F7.
The Fibonacci spiral
Squares with side lengths 1, 1, 2, 3, 5, 8 and 13 fit together without gaps to form a rectangle. Each side length is the sum of the two before it, so every new square fits exactly along the long side of the rectangle so far.
On squared paper, draw two squares of side 1 next to each other. Then add squares of side 2, 3, 5, 8 and 13, each along the long side of the rectangle, turning a quarter turn every time. In each square draw a quarter circle whose radius is the side length, so the arcs join up.
Each arc is about 1.6 times as big as the one before. That is why the figure looks like the golden spiral, which grows by the factor φ with every quarter turn. The two are close but not identical: the Fibonacci spiral is built from circular arcs, the golden spiral is a smooth logarithmic spiral. The rectangle has 13 · 21 = 273 unit squares, and so does the sum 1 + 1 + 4 + 9 + 25 + 64 + 169 of the squares. In general F12 + … + Fn2 = Fn · Fn+1.
The Fibonacci sequence in nature: what is true and what is not
The best-known example is the sunflower. In the flower head you see two families of spirals, one turning clockwise and one counterclockwise. Count both and you often find two neighboring Fibonacci numbers, such as 34 and 55 or 55 and 89. On pine cones the counts are usually 5 and 8 or 8 and 13.
The reason lies in how the plant grows. New seeds form at the growth point, each turned by the same angle from the one before. At about 137.5° no two seeds end up directly above each other, so the area fills evenly. This golden angle is 360° / φ2 ≈ 137.508°. It is linked to the sequence: multiply 360° by the fractions Fn / Fn+2 and the results close in on it. 2/5 gives 144°, 3/8 gives 135° and 21/55 gives 137.45°.
Nature does not follow the rule strictly, though. In 2016, Jonathan Swinton, Erinma Ochu and many volunteers analyzed 657 sunflower heads. In the most reliable set, 565 of 768 spiral counts were Fibonacci numbers, about three quarters. Another 67 belonged to related sequences such as the Lucas numbers, and 136 fit neither.
What is the Fibonacci sequence used for?
- Computer science: The slowest case of the Euclidean algorithm for the greatest common divisor is a pair of neighboring Fibonacci numbers, shown by Gabriel Lamé in 1844. The Fibonacci heap, a data structure by Michael Fredman and Robert Tarjan (1984), is named after the numbers in its analysis.
- Number theory: divisibility rules and identities such as the sum formula and the gcd rule above.
- Plant growth models: the golden angle and the spiral counts in sunflowers and cones.
- Teaching: a first example of a recursive sequence and of how a ratio can settle on a limit.
- Agile project planning: see the next section.
Fibonacci numbers as agile story points
Software teams that estimate work with “planning poker” often use cards labeled 1, 2, 3, 5, 8, 13 and 21. The game was named by James Grenning in 2002 and popularized by Mike Cohn. A common deck uses 0, ½, 1, 2, 3, 5, 8, 13, 20, 40 and 100, so it departs from the exact sequence at the top. The reasoning is that larger tasks are more uncertain, so the gaps between choices widen by roughly 60 percent. Teams then cannot claim a false precision like “17 versus 18.” The numbers measure relative size, not hours or days. Using Fibonacci numbers is a convention among teams and not a mathematical law.
A Fibonacci clock
A popular gadget shows the time with five squares of side lengths 1, 1, 2, 3 and 5. In the usual design the hour is the sum of the red squares and the minutes, in steps of five, are the sum of the blue squares times five. A square that counts for both is green, and a switched-off square is white. One possible display for 10:35: the hour is 10 = 5 + 3 + 2 and the minutes are 35 / 5 = 7 = 5 + 2. So the 5-square and the 2-square are green, the 3-square is red, and nothing is blue. Several combinations can show the same time, so the clock may pick any of them.
Fibonacci in Python
The recursive version copies the definition directly, which makes it easy to read but slow: fib(40) needs about 331 million function calls, because it recomputes the same values again and again.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)The iterative version keeps only the last two numbers and is fast. It starts with F0 = 0 and F1 = 1.
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print([fib(i) for i in range(10)])The last line prints [0, 1, 1, 2, 3, 5, 8, 13, 21, 34], and fib(100) returns 354224848179261915075. A third way keeps the recursive style but stores results that were already computed (memoization), for example with functools.lru_cache. The same ideas work in every language; in JavaScript the recursive version is function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }.
Practice problems with answers
On the same topic, the German pages offer a worksheet on number sequences and a sequence calculator (both in German) that recognizes the Fibonacci rule in a list of numbers.
Frequently asked questions
What is the Fibonacci sequence?
It is the list 1, 1, 2, 3, 5, 8, 13, 21, … in which each number is the sum of the two before it. The terms are called Fibonacci numbers. See the rule and first terms.
What is the formula for the Fibonacci sequence?
Recursively Fn = Fn−1 + Fn−2 with F1 = F2 = 1. Explicitly, by Binet’s formula, Fn = (φn − ψn) / √5. Examples are in the formula section.
What are the first 10 Fibonacci numbers?
1, 1, 2, 3, 5, 8, 13, 21, 34 and 55. If you start with 0, the first ten are 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34. All numbers up to F50 are in the table.
Does the Fibonacci sequence start with 0 or 1?
Both versions are in use: 0, 1, 1, 2, 3, … with F0 = 0, or 1, 1, 2, 3, … with F1 = F2 = 1. From F1 on they are the same.
Who invented the Fibonacci sequence?
Indian scholars of poetry knew it before Leonardo of Pisa. In Europe it appears first in his Liber abaci (1202), and it received its name from Édouard Lucas in the 19th century.
How is the Fibonacci sequence related to the golden ratio?
The ratio of two neighboring Fibonacci numbers gets closer and closer to φ ≈ 1.618, because q = 1 + 1/q has the solution φ. See the golden ratio section.
Where does the Fibonacci sequence appear in nature?
Reliably in the spiral counts of sunflower heads and pine cones, where about three quarters of the counts in a 2016 study were Fibonacci numbers. Many other claims, such as shells, galaxies and the human body, are not supported. Details are in the nature section.
What is the Fibonacci spiral?
It is a spiral of quarter circles drawn inside squares with side lengths 1, 1, 2, 3, 5, 8, 13 and so on. It resembles the golden spiral. How to draw it is explained in the spiral section.
Why are Fibonacci numbers used for story points?
Because the gaps between the numbers grow with their size. This discourages false precision when estimating large, uncertain tasks. It is a convention of agile teams, not mathematics. See story points.
Is there a Fibonacci Day?
Yes, informally. Fans celebrate it on November 23, because in the month-day format 11/23 gives the digits 1, 1, 2, 3. It is not an official holiday.
Sources and further reading
- Encyclopaedia Britannica: Fibonacci sequence
- Encyclopaedia Britannica: Fibonacci
- MacTutor History of Mathematics: Leonardo Pisano Fibonacci
- Jonathan Swinton, Erinma Ochu and others: Novel Fibonacci and non-Fibonacci structure in the sunflower, Royal Society Open Science 3 (2016), article 160091.
- Ron Knott: The Fibonacci Numbers and Golden Section in Nature
- Parmanand Singh: The So-called Fibonacci Numbers in Ancient and Medieval India, Historia Mathematica 12 (1985), pp. 229–244.
- Wikipedia: Planning poker and Wikipedia: Lamé’s theorem
Spotted a mistake or have a request? Send us a short message and we will take care of it.