Информация о задаче

Задача 78506

Тема:

[

Рекуррентные соотношения

]

Сложность: 4
Классы: 9,10

Прислать комментарий

Условие

Последовательность чисел a₁, a₂,..., a_n... образуется следующим образом:

a₁ = a₂ = 1; a_n = $\displaystyle {\frac{a_{n-1}^2+2}{a_{n-2}}}$ (n $\displaystyle \ge$ 3).

Доказать, что все числа в последовательности — целые.

Решение

Докажем индукцией по n равенство a_n = 4a_{n - 1} - a_{n - 2}. Проверка базы индукции при n = 3, 4 оставляется читателю в качестве упражнения. Докажем шаг индукции. Пусть при всех 2 < n < N доказываемое утверждение выполняется. Тогда

a_N = $\displaystyle {\frac{a_{N-1}^2+2}{a_{N-2}}}$ = $\displaystyle {\frac{(4a_{N-2}-a_{N-3})^2+2}{a_{N-2}}}$ = 16a_{N - 2} - 8a_{N - 3} + $\displaystyle {\frac{a_{N-3}^2+2}{a_{N-2}}}$ .

Так как a_{N - 2} = ${\frac{a_{N-3}^2+2}{a_{N-4}}}$ , последнее слагаемое равно a_{N - 4}. Следовательно,

a_N = 16a_{N - 2} - 8a_{N - 3} + a_{N - 4} = 4(4a_{N - 2} - a_{N - 3}) - (4a_{N - 3} - a_{N - 4}) = 4a_{N - 1} - a_{N - 2},

что и требовалось. Итак, при всех натуральных n выполнено равенство a_n = 4a_{n - 1} - a_{n - 2}, а значит, все числа последовательности целые.

Источники и прецеденты использования


олимпиада
Название	Московская математическая олимпиада
год
Номер	26
Год	1963
вариант
	1
Класс	10
Тур	2
задача
Номер	5