Cassini's identity 2026-10-20
For the Fibonacci numbers , , the identity holds for . It follows by induction: replacing each term using the Fibonacci recurrence negates the left-hand side when increases by one, and the value at is .
Divisibility sequence Created 2026-10-20 Updated 2026-11-05
A divisibility sequence is an integer sequence satisfying , with any conventions about zero terms stated. For example has this property because if , thenThe Fibonacci numbers also form a divisibility sequence. The stronger identity defines a strong divisibility property and does not follow from the basic implication alone. Such sequences organize common-factor questions by relationships among their indices.
Fibonacci addition formula 2026-10-14
With the standard Fibonacci numbers , , this identity holds for , . At it is immediate. If it holds for at every , apply it at and use to obtain , proving the assertion by mathematical induction. Taking gives for , linking the doubling formula to the Lucas numbers.
Fibonacci gcd reduction 2026-10-14
Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes for . Taking the greatest common divisor with removes the last summand, and multiplication by the coprime factor leaves that gcd unchanged. The case uses . Applying the Euclidean algorithm to the indices yields the strong-divisibility identity for nonnegative indices, with the usual zero conventions.
Fibonacci matrix Created 2026-10-20 Updated 2026-11-05
With , , the Fibonacci matrix advances consecutive Fibonacci numbers:Multiplying by proves the formula by induction. Since matrix powers obey , their entries give Fibonacci addition formulas. Exponentiation by squaring computes with matrix multiplications, including directly in modular arithmetic. The determinant identity also makes the update invertible modulo every positive integer.
Fibonacci multiple-index divisibility 2026-10-31
For positive integers , the Fibonacci numbers satisfy . The Fibonacci addition formula gives , so mathematical induction on proves the assertion. This explains why every fifth Fibonacci number is divisible by .
Fibonacci Nim Created 2026-10-20 Updated 2026-11-05
Fibonacci Nim is a normal play impartial game on one heap. Start with counters. The first move removes between and counters; thereafter a move removes at least one and at most twice the number just removed by the opponent, without exceeding the remaining heap. Taking the last counter wins.
For a position with counters and permitted maximum , let be the smallest Fibonacci number appearing in the Zeckendorf representation of , using the sequence . The position is losing exactly when . If , removing is a winning move. When this does not empty the heap, the next smallest summand exceeds , so the opponent's new limit is too small. Conversely, the Zeckendorf subtraction lemma gives whenever , so every legal move from a losing position leaves a winning one.[ref]
Fibonacci Nim by Michael J. Whinihan. Pages 9–12: rules, least-summand criterion and proof
Initially , so the losing initial heap sizes are precisely the Fibonacci numbers. For example, : take , leaving the opponent counters and a limit of , a losing position. The move limit is part of the state; heap size alone does not determine later positions.
Fibonacci polynomial Created 2026-10-20 Updated 2026-11-05
Fibonacci powers of the cat-map matrix Created 2026-10-31 Updated 2026-11-05
Use the standard Fibonacci number convention , , . For the cat map matrix,At , the right side is . To prove the induction step, multiply it by . The top-left entry becomes , the top-right becomes , and the lower row follows from the same recurrence. This advances all indices by two.
For example, , so two iterations send to modulo one. The formula turns repeated matrix multiplication into an explicit integer recurrence; the exponential growth of the Fibonacci numbers agrees with the expanding eigenvalue of the cat map.
Fibonacci recurrence 2026-10-18
The linear recurrence relation defining the Fibonacci numbers, with and . Its state advances by the matrix , so matrix powers describe repeated updates.
Fibonacci tree Created 2026-10-20 Updated 2026-11-05
A Fibonacci tree is a recursively defined binary tree whose two subtrees have consecutive smaller orders. One convention sets and to a single vertex and defines for by attaching and to a new root. Then its vertex count satisfies , so for Fibonacci numbers . The counts begin . Initial trees vary across applications, so the convention must be stated; the common feature is the consecutive-order recursive branching.
Generating function Created 2026-10-07 Updated 2026-10-14
A generating function packages a sequence into a series so that operations on objects become operations on their encodings. An ordinary generating function uses the power series ; in counting problems, the coefficient records the number of objects of size . The variable initially marks size: it need not be assigned a numerical value. Coefficient extraction writes this recovery as . One compact expression can therefore answer infinitely many counting questions, while explaining how their answers fit together.
Start with two contributions: choose from and from , with exactly one option at each allowed value. Their individual ordinary generating functions are the polynomials and . To count ordered pairs by total , multiply:The coefficients count the ways to obtain totals zero through three. For total two, the possibilities are and ; the two corresponding monomials both contribute . There are six ordered pairs altogether, agreeing with .
If the first contribution has two distinguishable choices when , replace by . Its product with becomes . The coefficients now carry multiplicities as well as possible totals; the exponent still records cost. This lets the same construction handle several actions with identical costs without losing their separate identities.
In general, the Cauchy product givesFor each split of the total size, the rule of product counts the choices of the two components; summing over those splits counts all possibilities. This requires each combined object to have a unique decomposition into the two components. The same idea works for costs, lengths, or other additive measures, not just the number of pieces. See MIT 18.310, generating functions, sections 1–2.
Now cover a board of length with tiles of lengths one and two, without gaps or overlaps. Let count these tilings. There is exactly one empty tiling, so , and . Removing the first tile leaves a board shorter by one or two, giving the recurrence relationThese are the Fibonacci numbers shifted by one index: under the convention , . Keeping the empty tiling is essential to both the counting rule and the resulting ordinary generating function.
Length-one and length-two tiles give five coverings of a length-four board and the Fibonacci recurrence
. Details. For , the empty board or a first tile followed by a remaining tiling givesEquivalently, : each factor chooses one tile, and counts pieces while the exponent of records total length. The same ordinary generating function counts ordered histories of two repeatable actions costing one and two units. Histories and differ despite having the same total cost. MIT's notes use dots and dashes with these costs, including the empty message. [ref]
These identities hold in formal power series algebra: each requested coefficient uses only finitely many contributions. The repeated-choice expansion is legitimate because has zero constant term; a zero-cost repeatable action would allow infinitely many histories of the same size. Numerical evaluation separately requires a convergent series. Here the radius of convergence is , the reciprocal of the golden ratio. At , the rational function equals , but the counting series diverges: that value cannot represent its sum.
Other generating functions change the encoding: an exponential generating function divides by factorials, while a Dirichlet series uses . A counting generating function also differs from a probability generating function, whose coefficients must be nonnegative and sum to one.
Golden ratio base Created 2026-10-20 Updated 2026-11-05
Golden ratio base is a positional notation with base . A finite digit string represents , usually using digits and allowing both positive and negative powers.
The identity gives the rewrite , so representations need a normalization convention. In particular, . Avoiding adjacent ones removes many finite ambiguities. This links an irrational numerical base to Fibonacci numbers and to symbolic rules for rewriting digit strings.
Integer sequence Created 2026-10-20 Updated 2026-11-05
An integer sequence is a sequence whose terms are integers. It can be specified by a formula, a recurrence relation, a counting interpretation or a finite computational rule. Examples include , the Fibonacci numbers and the prime numbers.
A finite prefix does not determine a unique infinite sequence. If a polynomial matches , adding leaves those values unchanged and usually changes later ones. Identifying a sequence therefore requires its definition, indexing convention and domain, rather than a few suggestive values alone.
Lucas number 2026-10-14
The Lucas numbers obey the same second-order recurrence as the Fibonacci numbers but start with , so their sequence is . For , . Substitution in the Fibonacci addition formula gives . Consecutive Fibonacci numbers are coprime by the Euclidean algorithm; since , Bézout's identity gives .
Memoization arithmetic and stack costs 2026-10-13
Under constant-cost lookup and integer addition, Memoized Fibonacci evaluation has time complexity in Big O notation, retaining values. A hash table needs its own lookup-cost assumptions; an array indexed by avoids hash collisions in this example. Memoization removes repeated bodies, but also pays for keys, lookups and retained answers. A workload without reuse can pay those costs without saving evaluations.
The call stack remains. Left-first recursion descends through arguments before returning, giving simultaneously active frames for . Therefore the auxiliary space complexity includes frames as well as table entries in the constant-size-value model. An iterative bottom-up dynamic programming calculation removes these recursive frames; retaining only the two previous Fibonacci numbers suffices when only the final value is wanted, but discards the table useful for later requests.
Exact Fibonacci numbers do not remain constant-size values. For , the recurrence relation gives , so the representation of as a binary number has order bits. With ordinary addition costing order bit operations on such operands, the additions cost order bit operations in total. Retaining all values also requires order bits of value storage, before keys and frame overhead. The linear bound counts additions under its stated cost model; it is not a linear bound on exact integer arithmetic in bits.[ref]
Lecture 15: Recursive Algorithms (6.006 Spring 2020) by Massachusetts Institute of Technology, 6.006 course staff. MIT 6.006 Spring 2020, Lecture 15: Recursive Algorithms, printed p. 3, final three bullets: growing Fibonacci bit lengths and addition cost
Memoization cache contract 2026-10-13
For a terminating pure function, a reusable entry must record its correct completed result, and equal memoization keys must imply equal results throughout the entry's memoization cache lifetime. Reusing that result must also preserve the behavior callers require. These conditions separate correctness from speed: a complete key can be correct even if it rarely repeats.
A procedure using deterministic computation can still have a required side effect. If a procedure returns and appends an audit record on every call, serving the second call from a table preserves the numerical answer but skips the second record. Likewise, if each call promises a fresh mutable list, returning the same stored mutable list changes observable sharing and allows a caller to damage later answers. Plain result reuse is unsuitable for those contracts.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.lru_cache: paragraph warning against functions with side effects, distinct mutable results, or impure time/random results
Completion matters for recursion. Suppose computing key needs key , and computing needs . A table containing only completed answers has no answer to return for the second ; remembering completed values does not make this directed cycle terminate. Marking a key
ACTIVE before descending detects re-entry, as in spreadsheet dependency evaluation, but detection is not a solution of the circular equations. If computation fails, clear its active mark and do not publish an unfinished value. The example using Fibonacci numbers avoids this issue through a strictly decreasing argument.The call counts above assume sequential execution and no eviction. Concurrent requests for an absent key can both begin evaluation before either publishes its result; keeping a table coherent alone does not ensure one body execution per key.[ref]
functools — Higher-order functions and operations on callable objects (Python 3.14 documentation). Python documentation, functools.cache and functools.lru_cache: thread-safe cache updates can still allow repeated evaluation before completion
Memoized Fibonacci evaluation Created 2026-10-13 Updated 2026-11-05
The Fibonacci numbers give an exact example. For a nonnegative integer , their recurrence relation isTo obtain by direct recursion, evaluate and separately; computing also evaluates . The full call tree has 15 occurrences but just six distinct arguments, . Shared dependencies form a directed acyclic graph because every directed edge goes to a strictly smaller argument. Memoization evaluates a distinct argument on first demand; filling values in increasing argument order is the corresponding bottom-up dynamic programming calculation.[ref]
Lecture 15: Recursive Algorithms (6.006 Spring 2020) by Massachusetts Institute of Technology, 6.006 course staff. MIT 6.006 Spring 2020, Lecture 15: Recursive Algorithms, printed pp. 2–3, Fibonacci Numbers and Re-using Subproblem Solutions
Repeated calls for Fibonacci numbers and their shared directed acyclic graph of dependencies
. The call tree contains 15 occurrences for . The dependency graph contains six distinct arguments and eight directed edges. Equal labels have equal colors; arrows in the right panel point from a caller to the value it requires. Details.Use an initially empty hash table
memo, shared by every recursive call. Count even the first evaluations of the two base cases, store only completed results, evaluate the left term first, and retain all entries. The following original procedure assumes a nonnegative integer argument:def cached_fib(n, memo):
if n in memo:
return memo[n]
if n < 2:
value = n
else:
value = cached_fib(n - 1, memo) + cached_fib(n - 2, memo)
memo[n] = value
return valueEvery self-call must pass through the memoization lookup. Wrapping only the outer call while leaving inner calls uncached retains the repeated work. Test membership rather than whether the stored value is nonzero: is a valid completed result.
For cold , the lookup arguments are . The first six are absent; the last three reuse completed answers. Results are stored on return in argument order , with values . Thus there are nine wrapper calls, six body evaluations and four additions. Repeating with the same table takes one wrapper call and no body evaluation. Requesting next evaluates only its body, reuses and , and stores : three wrapper calls, one body evaluation and two hits.
An exact memoization lookup trace and the effect of retaining or clearing its table
. The first row records cold lookup order. The table records successive requests with one retained table; clearing it before the final request restores the cold counts. Calls include lookups that immediately return stored values; bodies count only first evaluations. Details.The direct-call count satisfies and . Its exact solution is , as substitution into this recurrence relation verifies. With the specified memoization procedure, a cold call at evaluates distinct bodies, makes additions and makes wrapper calls. There are hits: each of the nonbase bodies issues two recursive calls, in addition to the initial call. The difference is between the number of occurrences and the number of distinct subproblems.
Represent each generated sequence position by an immutable head and a lazily memoized successor, and give each iterator its own pointer into the shared chain. Computing a successor invokes the privately owned generator once; lagging copies reuse that same successor. Consequently a mutable programming closure generating Fibonacci numbers can support interleaved independent cursor positions. Sharing only the generator and a copied current value would instead consume the generator's mutable state twice. This construction can retain all cells between the fastest and slowest live cursors; it does not guarantee constant memory usage.
Michael J. Whinihan 2026-11-05
Michael J. Whinihan published an analysis of Fibonacci Nim in 1963. His paper connects a take-away game with the unique decomposition of an integer into nonconsecutive Fibonacci numbers.[ref]
After the opening move, a player may remove at most twice the preceding player's removal. The smallest summand in the heap's Zeckendorf representation identifies the strategic threshold. Thus a numerical representation becomes operational information about a winning strategy: the relevant feature is not the heap's size alone but its least Fibonacci component.[ref]
Fibonacci Nim by Michael J. Whinihan. Winning-strategy construction



