Exercise 1040Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

Induction and periodicity

#induction#periodicity#recurrence

Statement

Let $(u_n)$ satisfy $u_{n+2}=u_{n+1}+u_n$ mod $10$ , with $u_0=0,u_1=1$ . Show the sequence is periodic.

Hint

The pair $(u_n,u_{n+1})$ takes values in $\{0,\ldots,9\}^2$ , finite.

Show solutionHide solution

Finiteness. The state $(u_n,u_{n+1})$ is in $\{0,\ldots,9\}^2$ , which has $100$ elements. By pigeonhole, two states repeat.

Determinism. The recurrence determines all future states from $(u_n,u_{n+1})$ , so once two states coincide, the sequence is periodic from there.

Conclusion. The sequence $(u_n\bmod10)$ is periodic.