Метод спуска, индукция и последовательное конструирование в ТЧ

Определим последовательность рекуррентно:

Заметим, что

Докажем по индукции громоздкое утверждение для каждого

База индукции:
– все очевидно.

Индукционный переход:
Предположим, что для всех где Докажем, что

Для этого покажем, что
Рассмотрим выражение:

Обозначим числитель:

По предположению индукции выполняется:

Подставляем:

но поэтому сравнение можно сократить:

Следовательно, Таким образом,

Докажем часть про Рассмотрим Пусть Тогда и Из рекуррентной формулы:

Так как то Следовательно, если

Таким образом, — общий делитель и
По индукционному предположению поэтому

Пусть теперь Тогда и
Из определения последовательности:

Так как то
Поскольку левая часть сравнима с по модулю

Следовательно, откуда
По индукционному предположению поэтому взаимно просто с Таким образом,

Осталось проверить, что последовательность возрастающая. Докажем по индукции, что для всех

База индукции ():
так что

Индукционный переход:
Предположим, что для некоторого Докажем, что Вычислим:

По индукционному предположению поэтому:

Следовательно, числитель положителен. Знаменатель поэтому то есть