Problem
NT-B2-M12-P012 A Recurrence Modulo \(m\)
#12
★★★☆☆ Level 3 of 5
Let \(u_{n+2}=3u_{n+1}+2u_n\), where \(u_0,u_1\) are integers. Prove that the sequence \(u_n\) modulo \(m\) is eventually periodic.
The state is the pair \((u_n,u_{n+1})\) modulo \(m\).
Modulo \(m\), there are only \(m^2\) possible pairs \((u_n,u_{n+1})\). Hence among the first \(m^2+1\) pairs, two coincide. From the first repetition onward, all later values are determined by the same recurrence, so the residue sequence repeats. This gives eventual periodicity.
Here the transition may be non-invertible, so we claim eventual periodicity rather than pure periodicity.