В далёком 1963 году на Московской математической олимпиаде была такая задача.
Последовательность чисел a[1], a[2], ..., a[n] образуется следующим образом:
a[1]=a[2]=1;
a[n]=(a[n-1]^2+2)/a[n-2] при n>2.
Докажите, что все числа этой последовательности - целые.
Тогда, как и сейчас, в школах было 11 классов. Эта задача была во второму туре олимпиады 10 класса на последнем месте. Похожие задачи в последнее время часто встречаются в вариантах национальных олимпиад разных стран.
Изначально непонятно, почему при делении на a[n-2] число будет оставаться целым. Умножим обе части формулы на a[n-2]:
a[n]a[n-2]=a[n-1]^2+2.
Это равенство верно для всех n, поэтому верно и
a[n+1]a[n-1]=a[n]^2+2.
Вычтем последнее равенство из предыдущего:
a[n+1]a[n-1]-a[n]a[n-2]=a[n]^2-a[n-1]^2
и немного преобразуем:
a[n+1]a[n-1]+a[n-1]^2=a[n]^2+a[n]a[n-2];
a[n-1](a[n+1]+a[n-1])=a[n](a[n]+a[n-2]);
(a[n+1]+a[n-1])/a[n]=(a[n]+a[n-2])/a[n-1].
Из этого видно, что выражение (a[n+1]+a[n-1])/a[n] всегда равно одному и тому же. А чему?
Вычислим a[3]=(a[2]^2+2)/a[1]=3. Тогда
(a[n+1]+a[n-1])/a[n]=(a[3]+a[1])/a[2]=4,
откуда
a[n+1]=4a[n]-a[n-1].
Отсюда и следует, что все члены последовательности a[n] являются целыми числами.
Два других решения этой задачи можно прочитать в сборнике, посвящённом Московским математическим олимпиадам 1958-67 годов.