Abstract: Linear recurrences are arguably one of the most underrated topics in mathematics. They are simple to understand, elegant in their simplicity, yet the study of linear recurrences is surprisingly complex. The popular knowledge of linear recurrences, for the general population, may be limited to the Fibonacci sequence and the associated golden ratio φ = 1.618034…. In this blog post, I share my own experiences with studying linear recurrences, and in doing so, hope to inspire many more to come to appreciate them as much as I did. We examine other recurrences, such as the Lucas numbers, and their interesting properties.
In 1202, the Italian mathematician Leonardo Fibonacci invented a thought experiment. This was the same man who travelled to the Islamic world and introduced Europeans to Arabic numerals, which are more efficient than the Roman numerals. He imagined a species of immortal rabbits that take one month to mature, and then breed from the second month onwards, forever. Whenever a pair of rabbits breed, they produce a new breeding pair. He notices that the cumulative number of pairs grows peculiarly:
1, 1, 2, 3, 5, 8, 13, …
where each subsequent number is the sum of the previous two terms. Whilst knowledge of this sequence had existed for centuries, Fibonacci popularised it, hence why we still attribute it to him.
Mathematicians noticed that the ratios of consecutive terms of this sequence converged towards the golden ratio φ = (1 + √5)/2. This can be elegantly visualised through the close similarities between the golden and Fibonacci rectangles. Algebraically, we know this is true because of the formula Fn = φn/√5 – (-φ-1)n/√5, and because |-φ-1| < 1, we know that the latter term converges to 0, leaving the first term to be dominant, and hence we can approximate Fn ≈ φn/√5.
Centuries later, the French mathematician Édouard Lucas discovered a similar sequence, with the same recurrence rule but instead the starting terms are L0 = 2 and L1 = 1. Lucas numbers are less famous, but their closed-form formula is more elegant, with Ln = φn + (φ-1)n. As such, Lucas numbers can be approximated by rounding φn, for n ≥ 2. Additionally, Lucas numbers have the nice property where Ln is prime only if n is 0, prime or a power of 2.
My journey with linear recurrences began much later, in the summer of 2019, when I last visited Melbourne before AMSIConnect 2026. I was fortunate enough to be invited to the AMOC School of Excellence, where I met many wonderful people and attended countless Olympiad lectures. One lecture that stuck with me was about linear recurrences, where I learned about the general closed-form formula for linear recurrences, involving the roots of their characteristic polynomials. With that, I began experimenting.
I found a class of degree-2 linear recurrences that, like the Fibonacci and Lucas numbers, can be approximated by rounding the powers of specific surds. This happens if one of the roots of the quadratic characteristic polynomial is between -1 and 1, in which case exponentiating it makes it vanish, leaving only the power of the other root.
Additionally, recurrence with u(0) = 0 also have the property that u(kn) is divisible by u(n), a fact that becomes intuitive when you consider modulo arithmetic. And that’s how I discovered that F2n/Fn = Ln, establishing a surprising link between the two aforementioned sequences. There are countless mindblowing properties about these sequences, and I highly encourage anyone interested in numbers to study and appreciate them as much as I have!
David Nachuan Chen
The University of New South Wales
