Software engineers use the Fibonacci numbers in two equally important contexts: to demonstrate their knowledge of recursion during interviews, and to plan their work using story points, which are time estimates but with plausible deniability. It was in the latter context that I noticed something about the Fibonacci sequence that I hadn’t before: each number is a little less than twice the preceding number, and in fact the difference is one of the earlier numbers in the sequence. If \(F_n\) is the \(n\)th Fibonacci number, then
\[ F_n = 2 F_{n-1} - F_{n-3} \]
I always find these kinds of things easier to understand with examples—and I was in a JavaScript-y mood this morning—so here’s an interactive visualization of this fact. Click or tap on one of the numbers to see how it’s determined by the one before it and the one three before it.
= 2 × − = −
This property is easy to prove. Let’s number the Fibonacci numbers \(F_n\) such that \(F_1 = 1\) and \(F_2 = 1\), and let’s only consider the case where \(n \geq 4\), since our result is nonsensical if we go any earlier in the sequence than that. The \(n\)th Fibonacci number is defined as
\[ F_n = F_{n-1} + F_{n-2} . \tag{1} \]
Likewise, the previous number is given by
\[ F_{n-1} = F_{n-2} + F_{n-3} . \]
Rearranging these terms, \[ F_{n-2} = F_{n-1} - F_{n-3} . \]
If we plug this expression for \(F_{n-2}\) back into (1), we get
\[ \begin{align*} F_n &= F_{n-1} + \left( F_{n-1} - F_{n-3} \right) \\ &= 2 F_{n-1} - F_{n-3} , \end{align*} \]
exactly as we wanted to prove. Nothing earth-shattering here, but hey—you try to make it through a backlog grooming meeting without doing any recreational mathematics.