ПВГ 2023, 11 класс, задача 9 (творческая III)
Последовательность целых чисел задана рекуррентно: , ,
Найти , где это наибольший общий делитель и .
Ответ
Ответ: .
Общий ответ: , поэтому, например, , так как , .
Решение.
1. Получим рекуррентную формулу:
Действительно, из формул имеем:
С другой стороны, , откуда
Аналогично,
Учитывая, что , получаем искомое соотношение и для нечетных индексов:
2. Докажем, при помощи индукции по рекуррентную формулу
Доказательство.
a. При база индукции верна: , так как .
b. Пусть формула
справедлива при всех .
c. При получаем
Подставляя в эту формулу
получаем
что совпадает с доказываемой формулой для .
3. Тогда
Для чисел одной четности положим . Тогда
и поэтому (учитывая что для четных , делится на , а для нечетных — не делится).
Откуда только для чётных чисел и . Но сейчас докажем, что это верно и для чисел и — разной чётности.
4a. Пусть теперь — нечетное число. Докажем, что нацело делится на . Действительно,
и
Поэтому
Учитывая, что , получаем, что
а поэтому .
4b. Пусть и — нечетные числа. Из равенства и индукции вытекает, что нацело делится на . Получаем
Учитывая, что , получаем .
4c. Наконец, пусть и числа разной четности, а именно — нечетное, — четное. Пусть и . По доказанному имеем . Используя то, что нацело делится на , получаем .
Откуда уже для произвольных чисел и .