C. Discrete Functions · Sequences and Series

The Fibonacci Sequence and Related Sequences

C1.5 C1.2 C1.4About 70 minutes

Learning goals

I can write the recursion formula for the Fibonacci sequence and generate its terms.
I can investigate and describe patterns in the Fibonacci sequence using tables and algebraic notation.
I can generate related sequences that use two previous terms.
I can use a Fibonacci-type recursion to model a counting problem.

Words to know

Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, …, where each term after the second is the sum of the two terms before it: t₁ = t₂ = 1, tₙ = tₙ₋₁ + tₙ₋₂.

Fibonacci-type (related) sequence
Any sequence that follows tₙ = tₙ₋₁ + tₙ₋₂ but starts with different first two terms, such as the Lucas numbers 1, 3, 4, 7, 11, ….

golden ratio (φ)
The number (1 + √5)/2 ≈ 1.618. The ratios of consecutive Fibonacci numbers get closer and closer to it.

conjecture
A statement you believe is true based on evidence (such as patterns in a table), but have not yet proved.

A rabbit puzzle from 1202

In 1202, Leonardo of Pisa, now known as Fibonacci, published a book of arithmetic called Liber Abaci (the copies that survive come from his revised edition of 1228). It includes a puzzle about rabbits: a pair of baby rabbits takes one month to grow up; after that, each adult pair produces one new pair every month, and no rabbits ever leave. Month by month, the number of pairs is

1, 1, 2, 3, 5, 8, 13, 21, …

Each month's count is the sum of the previous two months' counts, because last month's pairs are all still there, and every pair that existed two months ago is now an adult that has a new baby pair. The same numbers had been described centuries earlier by scholars in India who studied the rhythms of Sanskrit poetry. Today we call them the Fibonacci numbers.

The recursion formula

The Fibonacci sequence needs two starting terms, because each new term uses the two terms before it:

t₁ = 1, t₂ = 1, tₙ = tₙ₋₁ + tₙ₋₂, for n > 2

So t₃ = 1 + 1 = 2, t₄ = 1 + 2 = 3, t₅ = 2 + 3 = 5, and so on.

n	1	2	3	4	5	6	7	8	9	10	11	12
tₙ	1	1	2	3	5	8	13	21	34	55	89	144

The first 12 Fibonacci numbers.

Worked example

Example 1: Generating terms

In the Fibonacci sequence, t₁₃ = 233 and t₁₄ = 377. Find t₁₅, t₁₆ and t₁₂.

t₁₅ = t₁₄ + t₁₃ = 377 + 233 = 610
t₁₆ = t₁₅ + t₁₄ = 610 + 377 = 987
Work backwards with t₁₄ = t₁₃ + t₁₂: t₁₂ = 377 − 233 = 144 ✓ (matches the table).

t₁₅ = 610, t₁₆ = 987, t₁₂ = 144

Investigating patterns

The Fibonacci numbers are full of patterns. The curriculum asks you to find them through investigation: make a table, look for a pattern, state a conjecture, and test it on more terms.

Pattern 1: sums. Add up the first few terms:

1 = 1, 1 + 1 = 2, 1 + 1 + 2 = 4, 1 + 1 + 2 + 3 = 7, 1 + 1 + 2 + 3 + 5 = 12, 1 + 1 + 2 + 3 + 5 + 8 = 20

Each sum is one less than a Fibonacci number: 2 = 3 − 1, 4 = 5 − 1, 7 = 8 − 1, 12 = 13 − 1, 20 = 21 − 1. In algebraic notation:

t₁ + t₂ + … + tₙ = tₙ₊₂ − 1

Pattern 2: even terms. t₃ = 2, t₆ = 8, t₉ = 34, t₁₂ = 144 are even, and no others in the table are. Every third term is even. Reason: odd + odd = even, then odd + even = odd, then even + odd = odd, and the pattern odd, odd, even repeats forever.

Pattern 3: sums of squares. 1² + 1² + 2² + 3² + 5² + 8² = 104 = 8 × 13. In general, t₁² + t₂² + … + tₙ² = tₙ × tₙ₊₁. The picture below shows why.

Squares with Fibonacci side lengths fit together to make a rectangle. Its area is the sum of the squares, and also 8 × 13, the product of the last two Fibonacci numbers used.

Pattern 4: ratios. Divide each term by the one before it: 1 ÷ 1 = 1, 2 ÷ 1 = 2, 3 ÷ 2 = 1.5, 5 ÷ 3 ≈ 1.667, 8 ÷ 5 = 1.6, 13 ÷ 8 = 1.625, 21 ÷ 13 ≈ 1.615, 34 ÷ 21 ≈ 1.619, 55 ÷ 34 ≈ 1.618, 89 ÷ 55 ≈ 1.618…. The ratios get closer and closer to the golden ratio, φ = (1 + √5)/2 ≈ 1.618.

The ratio of each Fibonacci number to the one before it, graphed as a discrete function. The points close in on the dashed line at φ ≈ 1.618.

Worked example

Example 2: A related sequence

A sequence uses the Fibonacci rule but starts differently: t₁ = 1, t₂ = 3, tₙ = tₙ₋₁ + tₙ₋₂. (These are the Lucas numbers.) Write the first eight terms and compare them with the Fibonacci numbers.

t₃ = 3 + 1 = 4, t₄ = 4 + 3 = 7, t₅ = 11, t₆ = 18, t₇ = 29, t₈ = 47.
Ratios: 47 ÷ 29 ≈ 1.621, 29 ÷ 18 ≈ 1.611. They also approach 1.618!
Compare with Fibonacci (F): from the second term on, each Lucas number is the sum of the Fibonacci numbers on either side of its position. For example, the 4th Lucas number is 7 = F₃ + F₅ = 2 + 5, and the 5th is 11 = F₄ + F₆ = 3 + 8.

1, 3, 4, 7, 11, 18, 29, 47

Worked example

Example 3: Climbing stairs

You climb a staircase taking either 1 or 2 steps at a time. In how many different ways can you climb 6 steps?

Let wₙ be the number of ways to climb n steps. Count small cases: w₁ = 1 (1). w₂ = 2 (1+1 or 2). w₃ = 3 (1+1+1, 1+2, 2+1).
Think about your last move. It is either a 1-step (after climbing n − 1 steps in any way) or a 2-step (after climbing n − 2 steps in any way). So wₙ = wₙ₋₁ + wₙ₋₂, the Fibonacci rule.
w₄ = 3 + 2 = 5, w₅ = 5 + 3 = 8, w₆ = 8 + 5 = 13.

13 ways (wₙ is the Fibonacci number tₙ₊₁).

Worked example

Example 4: Working backwards

A Fibonacci-type sequence (tₙ = tₙ₋₁ + tₙ₋₂) has t₅ = 19 and t₆ = 31. Find t₁ and t₂.

Rearrange: tₙ₋₂ = tₙ − tₙ₋₁.
t₄ = t₆ − t₅ = 31 − 19 = 12
t₃ = t₅ − t₄ = 19 − 12 = 7, t₂ = 12 − 7 = 5, t₁ = 7 − 5 = 2
Check forwards: 2, 5, 7, 12, 19, 31 ✓

t₁ = 2 and t₂ = 5

Fibonacci numbers in nature: be careful

The numbers of spirals in sunflower heads, pine cones and pineapples are very often consecutive Fibonacci numbers (for example, 8 spirals one way and 13 the other on many pine cones). This is a real and well-studied pattern. But be careful with claims you may see online that the golden ratio is hidden in everything from famous paintings to the human body: many of those are exaggerated or untrue. Check claims by measuring, like a mathematician.

Just for fun

I was going to tell you a Fibonacci joke...

...but it's about as good as the last two put together.

Hands-on activity

Spiral hunt and staircase count

You need: a pine cone (easy to find under conifers in the fall), a pineapple, or a photo of a sunflower head; a marker or small stickers; and a staircase.

Look at the bottom of the pine cone. You will see spirals of scales curving to the left and others curving to the right. Mark one spiral and count around until you return to it. Count the spirals in each direction.
Are your two numbers consecutive Fibonacci numbers? Compare with a friend or a second cone.
On a staircase, find all the ways to climb the first 4 steps using 1- or 2-step moves. List them. Do you get 5?
Predict the number of ways to climb 10 steps.

What to look for: many pine cones show 8 and 13 spirals (some show 5 and 8, and a few cones don't follow the pattern at all). The 4-step ways are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2: 5 ways. For 10 steps: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ways.

Your turn

Write the recursion formula for the Fibonacci sequence and explain why it needs two starting terms.

In the Fibonacci sequence t₁₅ = 610 and t₁₆ = 987. Find t₁₇ and t₁₈.

Use the pattern t₁ + t₂ + … + tₙ = tₙ₊₂ − 1 to find the sum of the first 10 Fibonacci numbers.

Write the first seven terms of t₁ = 2, t₂ = 2, tₙ = tₙ₋₁ + tₙ₋₂. How do they compare with the Fibonacci numbers?

Is t₂₄ of the Fibonacci sequence even or odd? Explain.

A Fibonacci-type sequence has t₄ = 10 and t₅ = 16. Find t₁, t₂ and t₃.

More practice: warm-up

Write the next three terms: 1, 1, 2, 3, 5, 8, …

Write the first six terms of t₁ = 1, t₂ = 4, tₙ = tₙ₋₁ + tₙ₋₂.

Calculate 21 ÷ 13 to three decimal places.

What is the approximate value of the golden ratio?

Who is the Fibonacci sequence named after?

More practice: on your own

Verify the sum-of-squares pattern t₁² + … + tₙ² = tₙ × tₙ₊₁ for n = 7.

Investigate: add the odd-numbered terms t₁ + t₃ + t₅ + … + t₂ₙ₋₁ for n = 1, 2, 3, 4. Make a conjecture.

Write the first eight terms of the "tribonacci" sequence t₁ = 1, t₂ = 1, t₃ = 2, tₙ = tₙ₋₁ + tₙ₋₂ + tₙ₋₃.

How many ways can you climb 8 steps taking 1 or 2 steps at a time?

A Fibonacci-type sequence starts t₁ = a, t₂ = b. Write t₃ to t₆ in terms of a and b.

Challenge

A Fibonacci-type sequence has t₁ = 3 and t₆ = 38. Find t₂. (Use the result of the last question.)

Explain why the sum pattern t₁ + t₂ + … + tₙ = tₙ₊₂ − 1 is true. (Hint: rewrite each term as tₖ = tₖ₊₂ − tₖ₊₁.)

A tile path is 2 units wide. You fill it with 1-by-2 tiles (each tile can lie along the path or across it). Count the ways to tile a path of length 1, 2, 3 and 4, and explain why the counts are Fibonacci numbers.

Check your understanding

Quiz

What is the next Fibonacci number after 34 and 55?

Which recursion formula defines the Fibonacci sequence?

The ratios of consecutive Fibonacci numbers get closer and closer to:

The sum of the first 8 Fibonacci numbers is:

Which Fibonacci term is even?

A Fibonacci-type sequence has t₃ = 9 and t₄ = 14. What is t₂?

For parents and teachers

Big idea: Expectation C1.5 asks students to investigate recursive patterns in the Fibonacci sequence and related sequences and to represent the patterns in several ways (tables of values, algebraic notation). The emphasis is on investigating: build a table, notice a pattern, write it algebraically, test it.

How to help: Look for spirals together on a pine cone, pineapple or sunflower. Ask your teen to explain the staircase problem; explaining why the count follows the Fibonacci rule (the last move is a 1-step or a 2-step) is the deepest part of the lesson.

Common difficulties:

Giving only one starting term. The Fibonacci rule uses two previous terms, so it needs two starting terms.
Index slips in the patterns (tₙ₊₂ versus tₙ₊₁). Test every pattern with actual numbers from the table.
Believing every golden-ratio claim online. The spiral counts in plants are real; many claims about art and the human body are not.