Recurrences & Characteristic Equations

Why it works. Try $a_n = x^n$: the recurrence $a_{n+2} = pa_{n+1} + qa_n$ becomes $x^{n+2} = px^{n+1} + qx^n$, i.e. $x^2 = px + q$. So each root gives a solution, and because the recurrence is linear, any combination $Ar^n + Bs^n$ is a solution too. Two free constants match any two starting values, and a sequence is fixed by its first two terms, so these are all the solutions.

Spotting it. $2 \pm \sqrt3$ are the roots of $x^2 = 4x - 1$, so $s_n = (2 + \sqrt3)^n + (2 - \sqrt3)^n$ satisfies $s_{n+2} = 4s_{n+1} - s_n$ and is an integer. The second term is tiny, which pins down the floor.

Step 1. $s_0 = 2$, $s_1 = 4$, then $s_2 = 14$, $s_3 = 52$, $s_4 = 194$, $s_5 = 724$, $s_6 = 2702$.

Step 2. $0 < (2 - \sqrt3)^6 < 1$ (indeed $2 - \sqrt3 \approx 0.27$), so $(2 + \sqrt3)^6 = 2702 - (\text{a number in } (0, 1))$ and its floor is $2701$.

Step 3. The remainder is $701$.

Spotting it. $x^2 = 4x - 4$ is $(x - 2)^2 = 0$: a double root, so the solution has the form $(A + Bn)2^n$.

Step 1. $a_0 = A = 1$ and $a_1 = 2(A + B) = 4$, so $B = 1$ and $a_n = (n + 1)2^n$.

Step 2. Check: $a_2 = 4 \cdot 4 - 4 \cdot 1 = 12 = 3 \cdot 4$ ✓

Step 3. $a_{10} = 11 \cdot 1024 = 11264$, and the remainder is $264$.

Fibonacci has $r^2 = r + 1$, roots $\tfrac{1\pm\sqrt5}2$, hence Binet's formula. The constants come from the initial terms, and forgetting that a repeated root needs the extra factor $n$ is the standard error — check any closed form against $a_1$ and $a_2$ before using it.

For $a_n = 2a_{n-1} + 1$ with $a_0 = 0$ you can also just iterate: $a_n = 2^n - 1$. Generating functions earn their keep when the recurrence has a non-constant forcing term or a convolution, where telescoping and characteristic equations both fail.

Step 1 — characteristic equation $r^2 - 5r + 6 = 0$, roots $2$ and $3$.

Step 2 — $a_n = A\cdot2^n + B\cdot3^n$.

Step 3 — $A + B = 2$ and $2A + 3B = 5$ give $B = 1$, $A = 1$, so $a_n = 2^n + 3^n$. Check: $a_2 = 4 + 9 = 13$ and $5(5) - 6(2) = 13$ ✓

Spotting it. The forcing term $n$ is a polynomial of degree $1$, so look for a particular solution of the same shape, $cn + d$, and add the homogeneous part $C \cdot 2^n$.

Step 1. $cn + d = 2(c(n - 1) + d) + n$ for all $n$ means $c = 2c + 1$ and $d = -2c + 2d$, so $c = -1$ and $d = -2$.

Step 2. $a_n = C \cdot 2^n - n - 2$, and $a_0 = 0$ gives $C = 2$: $a_n = 2^{n+1} - n - 2$. Check: $a_1 = 1$ and $a_2 = 2 \cdot 1 + 2 = 4 = 8 - 4$ ✓

Step 3. $a_{10} = 2048 - 12 = 2036$, and the remainder is $36$.

Why it works. The fixed point $L$ satisfies $L = cL + d$; subtracting that from $a_n = ca_{n-1} + d$ cancels $d$ and leaves a pure multiple. Taking reciprocals of $a_{n+1} = \tfrac{a_n}{1 + ka_n}$ gives $\tfrac1{a_{n+1}} = \tfrac1{a_n} + k$. And modulo $m$ a recurrence of order $k$ has at most $m^k$ possible windows of $k$ consecutive terms, so some window repeats and from then on the sequence cycles.

Spotting it. A constant term spoils the pure geometric pattern; the fixed point $L = 3L + 4$, i.e. $L = -2$, removes it.

Step 1. $a_{n+1} + 2 = 3(a_n + 2)$, so $a_n + 2 = 3^{n-1}(a_1 + 2) = 3^n$ and $a_n = 3^n - 2$.

Step 2. $a_7 = 2187 - 2 = 2185$, so the remainder is $185$. Check the start: $a_1 = 1$, $a_2 = 7 = 9 - 2$ ✓

Spotting it. A fraction whose denominator is $1 + (\text{constant})a_n$: reciprocals turn it into an arithmetic sequence.

Step 1. $\dfrac1{a_{n+1}} = \dfrac{1 + 3a_n}{a_n} = \dfrac{1}{a_n} + 3$.

Step 2. $\tfrac1{a_1} = \tfrac12$, so $\tfrac{1}{a_{10}} = \tfrac12 + 9 \cdot 3 = \tfrac{55}{2}$ and $a_{10} = \tfrac{2}{55}$.

Step 3. $m + n = 57$.

Spotting it. Last digits of Fibonacci numbers follow the same recurrence mod $10$, so they are periodic. The period of the pair $(F_n, F_{n+1}) \bmod 10$ is $60$: the pair $(1, 1)$ first returns at $(F_{61}, F_{62})$.

Step 1. $2026 = 60 \cdot 33 + 46$, so $F_{2026} \equiv F_{46} \pmod{10}$.

Step 2. $F_{46} = 1836311903$, so the last digit is $3$. (Without the exact value: $F_{46} = F_{23}(F_{22} + F_{24})$, and the last digits of $F_{22}, F_{23}, F_{24}$ are $1, 7, 8$, giving $7 \cdot 9 = 63$, last digit $3$.)