Periodic Sequences

Try this

Step forward one term at a time and watch the small grid next to the clock. There are only $7 \times 7 = 49$ possible pairs of neighboring terms $(a_{n}, a_{n + 1})$ . Can the sequence go on forever without repeating?
When you reach the first repeated pair, what should happen next, in principle? Take a few more steps (or press “Run to the first repeat”) to check.
Set $m$ to $8$ and $q$ to $2$ . Is the pair that repeats this time the first pair? (Look at “Tail length $μ$ ”.)
Now set $q$ to $3$ . The tail disappears. What role does it play whether $q$ and $m$ are coprime?

If there are positive integers $T$ and $n_{0}$ such that $a_{n + T} = a_{n}$ for every $n \geq n_{0}$ , then ${a_{n}}$ is called a periodic sequence and $T$ is a period of it. If $n_{0} = 1$ (it cycles from the very start), it is called purely periodic. The smallest such $T$ is the least positive period. A sequence of integers need not be periodic itself, but its remainders mod $m$ often are: it is then called periodic mod $m$ .

Predict first

The sequence $a_{1} = 1, a_{2} = 2, a_{n + 2} = a_{n + 1} - a_{n}$ . What is $a_{2026}$ ?

Choose an answer first; then you can see the result.

Why

Theorem: an integer linear recurrence is always periodic mod m

Step 1 / 4

States
$a_{n + 2} \equiv 3 a_{n + 1} + a_{n} (mod 7)$ . The next term depends only on the two before it, so the pair of neighboring terms is the state of the sequence: once you know it, everything after it is determined.

$(a_{n}, a_{n + 1}) determines a_{n + 2}, a_{n + 3}, \dots$
Pigeonholes
A repeat
Why it cycles from the start

The same argument works for any sequence in which “the next term is determined by the previous $k$ terms, and each term takes only finitely many values”: there are finitely many states, so sooner or later one repeats, and after the repeat the sequence cycles.

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: The sequence is purely periodic mod $m$ (it cycles from the very first term)

$a_{n + 2} \equiv a_{n + 1} + 3 a_{n} (mod 8)$ , $a_{0} = a_{1} = 1$ , and $(3, 8) = 1$ . Press “Run to the first repeat”: the pair that repeats is exactly the first pair, $(1, 1)$ .

Practice

Exercise 1Basic

$a_{1} = 3, a_{2} = 5, a_{n + 2} = a_{n + 1} - a_{n}$ . Find the sum of the first $100$ terms.

Exercise 2Basic

What is the last digit of $3^{2026}$ ?

Exercise 3Advanced

$a_{0} = 0, a_{1} = 1, a_{n + 2} = 2 a_{n + 1} + a_{n}$ . What is the least positive period of the sequence mod $7$ ?

Exercise 4Challenge

$a_{1} = 2, a_{n + 1} = \frac{1 + a _{n}}{1 - a _{n}}$ . Find $a_{2026}$ .

Try this

Why

Theorem: an integer linear recurrence is always periodic mod m

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Combining two periods and thinking only of the least common multiple