The Fibonacci Numbers — Exposed More Discretely (Benjamin & Quinn)
Researched by Arthur T. Benjamin from Harvey Mudd College and Jennifer J. Quinn from Occidental College and published on June 1st, 2003, The Fibonacci Numbers — Exposed More Discretely is a paper that discusses various proofs within the Fibonacci and Lucas sequences through an intuitive, discrete series of arguments while also generalizing it. This review offers insights on the key ideas, methodologies, and results of the research.
This research paper’s primary aim is to inform the readers about the unique properties of the Fibonacci and Lucas sequences and convey the idea of unity in mathematics by applying combinatorial methods to complete proofs.
This paper is significant because it explains a new method to explaining the patterns previously observed in the Fibonacci and Lucas sequences. Applying a discrete approach, it virtually eliminates the need for algebra or complex mathematics, instead focusing on intuitive, logical, and visual representations. Similar to how C(n, k) = C(n, n−k) can be proved algebraically but also by answering the question of choosing k from n or not choosing n−k from n, the discrete approach developed is used to prove each of the identities in the paper.
The key visual representation employed by the authors is of counting combinations of tilings with length n (Benjamin & Quinn, 2003, p. 183). This method replaces the algebraic approach of a Kalman and Mena paper that had inspired them to make for a more intuitive approach and illustrate how different approaches often yield the same results in mathematics. Each tiling is composed of 1×1 squares, each of which has a possible colors, or 1×2 dominoes, each of which has b possible colors. Recursion is used to generate a tiling of length n, denoted Fₙ, in terms of smaller tilings; for instance, since Fₙ ends in either a square or domino, it can be broken by casework into Fₙ₋₁·a + Fₙ₋₂·b, yielding the equation Fₙ = aFₙ₋₁ + bFₙ₋₂, which matches the general Fibonacci sequence, and matches the famous case when a = b = 1.
Breakability is used to extend the previous idea. In short, breakability is the concept of how many n-colored tiles can be split at cell m and how many cannot (Benjamin & Quinn, 2003, p. 183). To be breakable, the tiling is made up of a colored m-tiling followed by a colored n−m tiling, meaning that there are Fₘ·Fₙ₋ₘ such possible tilings. To be unbreakable at the m-th cell, the tiling has a colored m−1 tiling followed by a colored domino on m and m+1 and an n−(m+1) = (n−m−1)-tiling; there are b·Fₘ₋₁·Fₙ₋ₘ₋₁ such tilings when we consider that the domino may be of any of b colors. Combining the two cases forms the identity. To demonstrate the summation identity, the authors consider a tiling partition based on white squares, picking the last non-white square and summing the results. The idea is generalizable, considering not only non-white squares, but squares that are not of any of c different colors (Benjamin & Quinn, 2003, p. 184).
Building off breakability, the authors then define faults, where two stacked tilings are simultaneously breakable, and implement a tail-swap (switching ends at the final fault) to prove Cassini’s identity. The tail-swap mechanism turns two length-n tilings into an n−1 and n+1 length tiling; adding an error term to account for a not-fully-one-to-one relation (Benjamin & Quinn, 2003, p. 186), this arrives at Cassini’s identity, which states Fₙ² = Fₙ₋₁Fₙ₊₁ ± (−b)ⁿ⁺¹; keep in mind that this reduces to simply Fₙ₋₁Fₙ₊₁ ± (−1)ⁿ⁺¹ for the Fibonacci sequence with a = b = 1. This is easy to verify; for instance, F₇ = 13, F₈ = 21, and F₉ = 34 ⇒ 21² = 441 = 442 − 1 = 13·34 − 1, as expected.
The greatest common divisor (gcd) property, also proved in the paper through combinatorics, states that the gcd of any two Fibonacci numbers will be another Fibonacci number, one with index equal to the gcd of the two elements’ indices. Stated mathematically, this yields gcd(Fₙ, Fₘ) = F_gcd(n,m), which is supported by simple examples such as gcd(5, 8) = gcd(F₅, F₆) = F_gcd(5,6) = F₁ = 1 and gcd(1548008755920, 498454011879264) = gcd(F₆₀, F₇₂) = F_gcd(60,72) = F₁₂ = 144. For known values and indices of the sequence, this offers a path to trivially finding common factors and reduces computations.
Lucas Numbers are approached by the authors in a largely similar way, through bracelets. These extend the tiling strategy to a circle and have properties of being in- and out-of-phase that are analogous to the linear tilings’ breakability property.
In addition to a, b ∈ ℤ, a, b ≥ 0, Benjamin and Quinn also extended the sequences to more generalized values. Through the consideration of a random, infinitely long tiling, they were able to prove Binet’s formula, Fₙ = (1/√5)[((1+√5)/2)ⁿ − ((1−√5)/2)ⁿ] (Benjamin & Quinn, 2003, p. 192).
This paper provides a deeper layer of appreciation of the sequences, and mathematics in general, by revealing how two wholly different approaches converge to the same elegant results. In the context of the Fibonacci and Lucas sequences, Benjamin and Quinn are able to make properties memorable and understandable, intuitive in a way that previous proofs were not.