Задача
NT-B2-M12-P012 Рекурсия по модулю
#12
★★★☆☆ Уровень 3 из 5
Пусть \(u_{n+2}=3u_{n+1}+2u_n\), где \(u_0,u_1\) — целые. Докажите, что последовательность \(u_n\) по модулю \(m\) с некоторого места периодична.
Состояние задаётся парой \((u_n,u_{n+1})\) по модулю \(m\).
По модулю \(m\) существует только \(m^2\) возможных пар \((u_n,u_{n+1})\). Поэтому среди первых \(m^2+1\) пар две совпадут. Начиная с первого повторения, дальнейшие значения полностью определяются той же рекуррентной формулой, значит последовательность остатков будет повторяться. Это даёт периодичность с некоторого места.
Здесь переход может быть необратимым, поэтому утверждаем предпериодичность, а не чистую периодичность.