In the 1970 MAA High School Mathematics Contest (Problem #16), students investigated this unusual recurrence relation:

Let $F(n)$ be a sequence with initial conditions $F(1) = 1, F(2) = 1, F(3) = 1$, and defined for $n \ge 3$ by: $$F(n+1) = \frac{F(n) \cdot F(n-1) + 1}{F(n-2)}$$ Find the value of $F(6)$.

Normally, when a sequence divides by earlier terms, fractions with messy denominators quickly appear. But calculate the first few terms by hand:

• $F(4) = \frac{F(3) \cdot F(2) + 1}{F(1)} = \frac{1 \cdot 1 + 1}{1} = 2$
• $F(5) = \frac{F(4) \cdot F(3) + 1}{F(2)} = \frac{2 \cdot 1 + 1}{1} = 3$
• $F(6) = \frac{F(5) \cdot F(4) + 1}{F(3)} = \frac{3 \cdot 2 + 1}{1} = \mathbf{7}$
• $F(7) = \frac{F(6) \cdot F(5) + 1}{F(4)} = \frac{7 \cdot 3 + 1}{2} = \frac{22}{2} = \mathbf{11}$!
• $F(8) = \frac{F(7) \cdot F(6) + 1}{F(5)} = \frac{11 \cdot 7 + 1}{3} = \frac{78}{3} = \mathbf{26}$!
• $F(9) = \frac{F(8) \cdot F(7) + 1}{F(6)} = \frac{26 \cdot 11 + 1}{7} = \frac{287}{7} = \mathbf{41}$!

Amazingly, the division is always exact! Every single term is an integer!

This phenomenon is related to the famous Somos sequences and the Laurent phenomenon in modern cluster algebras.

In this lesson, we will store the sequence in an array, compute its terms, and verify that the remainder is always zero!

Move the mouse over a dotted box for more information.

Notice how the terms grow: $1, 1, 1, 2, 3, 7, 11, 26, 41, 97, 153, 362, \dots$ Even with divisions by 7, 11, and 26, the numerator is always an exact multiple of the denominator!