Последовательности нестандартного вида

Значение не имеет значения, так как поэтому можно предположить, что

______________________________________________________________________________________________________________________________________________________

Лемма. для всех

Доказательство. Предположим обратное для получения противоречия. Пусть будет наименьшим числом, для которого Заметим, что Следовательно, и Таким образом, не может быть, что поэтому должно быть Поскольку то Таким образом, получаем что

Пусть будет наименьшим индексом, при котором Тогда как показано выше, но также

• если тогда и
• если тогда

Из минимального выбора следует, что И поскольку по минимальному выбору мы имеем Чтобы было должно быть

так что Соединив всё вместе, получаем

Это противоречит

______________________________________________________________________________________________________________________________________________________

Для завершения решения докажем, что по индукции. Случаи даны. Предположим, что это верно для всех неотрицательных целых чисел, меньших где Существует два случая:

Случай 1:

Тогда

По индуктивному предположению одно из не меньше а другое, согласно лемме, не меньше Следовательно,

Таким образом, как и требовалось.

Случай 2:

Поскольку мы определили существует индекс такой что при котором

Мы имеем

Таким образом,

Теперь утверждаем, что Это верно, поскольку для утверждение проверяется напрямую; для одно из не меньше по индуктивному предположению, а другое, согласно лемме, не меньше 1. Следовательно, как утверждалось, и поэтому по последнему неравенству в предыдущем абзаце.

Так как и, согласно лемме, из мы получаем следующие два неравенства:

Теперь заметим, что

В силу того, что

Следовательно,

Таким образом, как и требовалось.