Так вот — давайте эту последовательность ψ_k приводить по какому-нибудь модулю, по которому m чему-нибудь хорошему равно. А именно: если m сравнимо с 2 по модулю N, то приведение по модулю N превращает соотношение на ψ_k в
ψ_{k+1}= 2 ψ_k - ψ_{k-1},
а это соотношение арифметической прогрессии. Поэтому тогда ψ_k сравнимо со своим номером k.

А если m сравнимо с 3 по модулю N, то соотношение превращается в
ψ_{k+1}= 3 ψ_k - ψ_{k-1},
а это как раз соотношение на числа Фибоначчи F_{2k} с чётными номерами! То есть ψ_k сравнимо с F_{2k} по модулю N.