PaperlayerView exact revision on arXiv

Source-linked AI summary

Rotating-Memory Fibonacci Numbers and Periodic Tilings

Walid Abdelaidoum, El-Mehdi Mehiri, Hacène Belbachir

arXiv:2609.12569v1math.COcs.DM

TL;DR

The paper addresses how to analyze Fibonacci-type recurrences when the number of preceding terms used varies periodically. It defines a rotating-memory family and studies its algebraic and combinatorial structure, including geometric tiling models for periods 2 and 3.

  • Problem

    Most familiar Fibonacci generalizations keep a fixed recurrence order, while variable-order recurrences allow broad variation; this paper studies the structured case of periodically cycling memory lengths.

    Source: §1 · p. 2

  • Method

    The paper analyzes a recurrence whose memory cycles through 2, 3, …, k+1 and interprets it through endpoint-periodic tilings and restricted compositions.

    Source: §1 · p. 2

  • Results

    The recurrence has a simple multiplicative structure, and its period-2 and period-3 sequences have geometric realizations in triangular-chain and double-hexagon-strip tilings, respectively.

    Source: §1 · p. 2, §3 · p. 5

  • Takeaways & Limitations

    The tiling model provides a bijective explanation for the multiplicative factor accumulated over a complete memory cycle.

    Source: §8 · p. 18

Abstract

from arXiv · show

We introduce and study the rotating-memory Fibonacci numbers, a periodic variable-order analogue of the Fibonacci sequence in which the number of preceding terms used in the recurrence changes cyclically with the index. Despite this varying memory, the resulting sequences exhibit a remarkably rigid structure. We derive closed forms, rational generating functions, arithmetic properties, and exact growth behavior, and show that the sequence decomposes naturally into geometric subsequences. We also develop combinatorial interpretations in terms of periodically constrained tilings, and restricted compositions, including bijective explanations for the multiplicative structure of the sequence. In addition, the first two nonclassical periods admit natural geometry-driven realizations: the period-2 sequence arises from monomer--dimer tilings of a triangular chain, while the period-3 sequence is related to tilings of a double hexagon strip by single and double hexagons. These connections provide geometric interpretations of the rotating recurrence in which the periodic behavior is induced by the underlying structures themselves, and suggest a broader problem of constructing analogous models for higher periods.

1 Introduction

The paper studies a Fibonacci-type recurrence whose memory length cycles periodically, a structured alternative to more freely varying orders. It analyzes the resulting multiplicative structure and develops both position-dependent combinatorial models and geometric realizations for periods 2 and 3.

1 Introduction

  • The paper situates these models among prior work on higher-order Fibonacci recurrences and tiling interpretations of linear recurrences.It cites Miles for an early systematic treatment of higher-order Fibonacci sequences, and Benjamin, Derks, and Quinn for weighted tiling models of linear recurrences.Source: §1 · p. 2
  • The paper focuses on variable-order Fibonacci recurrences whose memory length cycles consecutively through 2, 3, …, k+1, rather than varying freely with the index.This structured subclass aims to retain enough regularity for explicit analysis while differing from fixed-order sequences.Source: §1 · p. 2
  • A periodically constrained tiling model makes the admissible tile length depend on its right endpoint, translating the recurrence into a last-tile decomposition.The same model has a restricted-composition interpretation in which admissibility depends on the partial sum where a part ends.Source: §1 · p. 2
  • For period 2, the RM-Fibonacci terms enumerate monomer–dimer tilings of a triangular chain when one boundary vertex is prescribed to be a monomer.The sequence agrees, up to an initial shift, with OEIS A038754.Source: §1 · p. 2
  • For period 3, the shifted RM-Fibonacci sequence coincides with A354541, which counts double-hexagon-strip tilings by single and double hexagons.The paper presents this and the triangular-chain model as geometric realizations in which periodicity comes from the underlying structure.Source: §1 · p. 2

2 Rotating-Memory Fibonacci Numbers

This section defines the period-k RM-Fibonacci sequence through a cyclic memory rule and introduces its initial values. The memory lengths range from 2 through k+1, with the classical Fibonacci sequence recovered at period 1.

2 Rotating-Memory Fibonacci Numbers

  • For period k, the memory length is the periodic function ℓ_k(n) = 2 + (n mod k), cycling through 2, 3, …, k+1.Terms with negative indices are understood to be zero.Source: §2 · p. 3
  • At period 1 the sequence is classical Fibonacci; at periods 2 and 3, the memory cycles through 2–3 and 2–3–4, respectively.These small-period cases illustrate the rotating rule.Source: §2 · p. 3
  • Table 1 collects initial values of the RM-Fibonacci sequences for periods k = 1 through 5.The section also identifies an initial transient before the sequence's later structure becomes rigid.Source: Table 1 · p. 4, §2 · p. 4

3 Collapse of the Rotating Recurrence

The period-collapse theorem shows that the periodically varying recurrence simplifies after its initial transient. Its consequences include geometric subsequences, exact periodic ratios, and explicit arithmetic structure.

3 Collapse of the Rotating Recurrence

  • At non-reset positions the sequence doubles, while the reset transition contributes a factor of 3/2; together these yield the period multiplier.The multiplier is accumulated over one complete cycle of k transitions.Source: §3 · p. 5
  • After the initial transient, the sequence satisfies a sparse constant-coefficient recurrence, with each residue class modulo k evolving geometrically.The period multiplier is c_k = 3 · 2^(k−2), and successive blocks repeat the shape 1, 2, 4, …, 2^(k−1) while scaling by c_k.Source: §3 · pp. 5–6
  • For every k ≥ 4, all terms after the initial transient are 3-smooth, with no prime divisors other than 2 and 3.Source: §3 · p. 6
  • From n = 4 onward, consecutive-term ratios are periodic with period k, making the sequence’s periodic modulation exact after finitely many terms.This exact ratio behavior supports deriving closed forms, generating functions, and growth results without periodic matrix products.Source: §3 · p. 6
  • The RM-Fibonacci recurrence fits the broader framework of conditional recurrences, but its staircase pattern of periodic zero-one coefficients produces a sparse reduction and exact ratios.The paper contrasts its varying memory length with periodic-coefficient Fibonacci recurrences that retain order two.Source: §3 · p. 6

4 Closed Forms, Generating Functions, and Growth

The section uses period collapse to derive closed forms, arithmetic properties, rational generating functions, and exact growth behavior for RM-Fibonacci numbers. These results expose a periodically modulated exponential structure.

4.1 Closed forms

  • For periods 2 and 3, the closed-form constants are c_2=3 and c_3=6, respectively.The corresponding stated values are R(2)_3=1 and R(3)_3=2.Source: §4.1 · p. 7
  • For k≥4, the closed form determines the exact powers of 2 and 3 in each term.The exponent of 3 counts completed memory cycles, while the exponent of 2 depends on both cycle number and position within the cycle.Source: §4.1 · p. 7
  • The sums of complete blocks also have simple closed forms.Source: §4.1 · p. 7

4.2 Rational generating functions

  • After a finite initial transient, RM-Fibonacci numbers are C-finite and have a rational ordinary generating function.Multiplying the generating function by 1−c_k x^k gives a polynomial numerator whose coefficients vanish from degree 2k onward.Source: §4.2 · pp. 8–9
  • The equal modulus of all characteristic roots produces growth modulation by the residue class of n.The section gives an exact periodically modulated exponential form for the sequence.Source: §4 · p. 7, §4.2 · p. 9

4.3 Exponential growth

  • The growth rate ρ_k increases strictly with k and approaches 2, while remaining below 2 for every finite period.Within each period, k−1 transitions double the sequence and one reset transition has factor 3/2.Source: §4.3 · p. 10
  • The global exponential growth rate is the geometric mean of the k local multipliers in one memory cycle.Consecutive terms alternate between two exact local growth factors.Source: §4.3 · p. 10

5 Periodic Tilings and Restricted Compositions

The section translates rotating memory into endpoint-periodic tilings and restricted compositions, then gives bijective explanations for the doubling and ternary factors that combine into the period multiplier.

5.1 Endpoint-periodic tilings

  • RM-tilings use tile lengths permitted by the right endpoint, so removing the final tile leaves an admissible tiling and recovers the rotating recurrence.The shifted sequence is normalized for tiling enumeration.Source: §5.1 · p. 11, §5 · p. 11

5.2 Restricted compositions

  • The number of k-rotating compositions of n equals R(k)_{n+1}, with each part’s admissibility determined by the partial sum where it ends.This periodic condition depends on accumulated size, not the part number.Source: §5.2 · p. 12

5.3 A bijective explanation of doubling

  • At non-reset positions, each extension has two choices: append a length-1 tile or extend the final tile, explaining the doubling factor.Each non-reset step contributes an independent binary decision.Source: §5.3 · p. 13

5.4 The ternary transition across a reset

  • At a reset, the terminal length-1 class supplies two additional copies, giving a combinatorial explanation for the factor 3.The reset transition is combined with the immediately preceding step.Source: §5.4 · p. 13

5.5 A combinatorial proof of the period-collapse theorem

  • A complete memory cycle corresponds to one ternary choice and k −2 independent binary choices, yielding the multiplier 3 · 2^(k−2) after the initial transient.The stated bijection applies for k ≥2 and n ≥k −1.Source: §5.5 · pp. 13–14

6 The Period 2 Case and Monomer-dimer Tilings

The period-2 sequence is realized by monomer–dimer tilings of a triangular chain with its leftmost vertex prescribed as a monomer. The terminal vertex’s parity determines the recurrence order.

The period-2 geometric realization

  • For graph G_n, the number a_n of monomer–dimer tilings with leftmost vertex v1 forced to be a monomer satisfies exactly the period-2 RM-Fibonacci recurrence.The initial values are a1 = 1, a2 = 1, and a3 = 2; for n ≡ 1 (mod 2), a_n = a_{n−1} + a_{n−2} + a_{n−3}.Source: §6 · p. 14
  • The terminal vertex has one dimer partner when n is even, but two when n is odd, producing the alternating recurrence cases.For odd n, pairing with v_{n−2} forces v_{n−1} to be a monomer.Source: §6 · p. 15
  • Without the prescribed boundary monomer, the total number of tilings of G_n is 2R(2)_n for n ≥2.The two cases are whether v1 is a monomer or belongs to the dimer {v1, v2}.Source: §6 · p. 15
  • The sequence is a shifted form of OEIS A038754, and the triangular-chain model supplies an additional monomer–dimer interpretation.The passage gives R(2)_n = A038754(n −2) for n ≥2.Source: §6 · p. 15

7 The period-3 Case and Double-Hexagon Tilings

The period-3 sequence has a geometric realization as tilings of a double-hexagon strip by single and double hexagons. A terminal decomposition yields the rotating recurrence, and an explicit bijection connects these tilings to period-3 RM-tilings.

The period-3 geometric realization

  • The strip’s terminal configurations depend on n modulo 3, and their decompositions produce the periodic recurrence for the tiling counts.When n ≡1 (mod 3), the recurrence includes H_{n−1} + 2H_{n−2}; when n ≡2 (mod 3), it includes H_{n−1} + H_{n−2}.Source: §7 · pp. 15–17
  • The shifted period-3 RM-Fibonacci numbers enumerate double-hexagon-strip tilings by single and double hexagons and coincide with OEIS A354541.The tilings can also be connected explicitly to period-3 RM-tilings by a bijection.Source: §7 · pp. 15, 17, 18
  • The explicit bijection replaces each admissible RM tile with a hexagonal configuration and recovers a unique RM-tiling by reversing the terminal decomposition.The terminal cases distinguish single hexagons and the possible adjacent double-hexagon configurations.Source: §7 · pp. 17–18
  • The period-3 sequence therefore has two distinct tiling interpretations, with Theorem 10 explaining their equality at the level of objects.The passage identifies these as the RM-tiling model and the double-hexagon-strip model.Source: §7 · p. 18

8 Concluding Remarks and Open Problems

The paper presents algebraic and combinatorial structure for RM-Fibonacci numbers, including a bijective account of the multiplier accumulated over a memory cycle. It closes by proposing extensions to higher periods, other memory patterns, and nonperiodic rules.

Concluding remarks

  • RM-Fibonacci numbers exhibit period collapse, explicit formulas, rational generating functions, and exact exponential growth despite their periodically changing memory length.The combinatorial models include endpoint-periodic tilings, restricted compositions, and directed lattice paths.Source: §8 · p. 18

Concluding remarks and open problems

  • Geometry-driven tiling realizations are established for periods 2 and 3, while finding analogous models for each k ≥4 is posed as an open problem.The proposed models would ideally induce the recurrence cycle through geometry rather than an explicitly position-dependent rule.Source: §8 · p. 18
  • The conclusion identifies open directions in classifying memory patterns, extending the principle to other recurrences, and studying aperiodic or random rules.The paper asks which periodic patterns retain structural simplifications and where strong algebraic structure ceases to persist.Source: §8 · pp. 18–19
Loading 2609.12569v1…