Индукция во всём многообразии

Школьники и студенты обычно неплохо понимают суть метода математической индукции, но сталкиваются с проблемами при его практическом применении. Ну хорошо, мы предположили справедливость утверждения для какого-то конкретного случая — и как отсюда вывести справедливость случая следующего?

Мой ответ не балует разнообразием: как угодно! Лишь бы в результате удалось получить требуемое!

Вашему вниманию предлагается краткое содержание части занятия с первокурсниками, на котором это «как угодно» было выполнено тремя способами для одной задачи.

Доказать, что при всяком натуральном \(n\) справедливо неравенство \(2^n>n\).

С основанием индукции никаких проблем не возникло: действительно, совершенно очевидно, что \(2^1>1\), и здесь всё в порядке. Нужно было показать переход, и вот здесь-то началось самое настоящее математическое творчество.

Способ первый

Студент сказал: мне нужно из предположительно справедливого \(2^n>n\) вывести неравенство \(2^{n+1}>n+1\). Хорошо, я возьму это предположительно справедливое неравенство и умножу обе его части на \(2\), сохранив справедливость. Получится \(2^{n+1}>2n\) и далее можно записать

\[
2^{n+1}>2n=n+n\geqslant n+1.
\]

Это именно то, что требуется, индукционный переход удался и тем самым утверждение доказано полностью.

На мой взгляд, здесь мы видим самое короткое и простое доказательство из всех возможных — во всяком случае, лично я и сам бы доказывал именно так. Но у двух других студентов обнаружились собственные взгляды на проблему.

Способ второй

Другой студент сказал: а я буду вместо исходного неравенства доказывать эквивалентное ему:

\[
\frac{2^n}n>1.
\]

Основание индукции для него проверяется столь же легко и далее мне нужно, предположив справедливость \(\frac{2^n}n>1\), вывести отсюда неравенство \(\frac{2^{n+1}}{n+1}>1\).

Рассмотрим очевидное неравенство \(2\geqslant1+\frac1n\) и представим его в следующем виде:

\[
\frac{2^{n+1}}{2^n}\geqslant\frac{n+1}n.
\]

Перемножая это неравенство как пропорцию, получаем

\[
\frac{2^{n+1}}{n+1}\geqslant\frac{2^n}n.
\]

Если теперь воспользоваться сделанным предположением, то получается цепочка

\[
\frac{2^{n+1}}{n+1}\geqslant\frac{2^n}n>1.
\]

Переход удался, и утверждение доказано полностью.

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

Способ третий

Студентка сказала: а я воспользуюсь школьной формулой разности натуральных степеней! Вот как можно записать:

\[
2^{n+1}-1 = (2-1)(2^n+2^{n-1}+\cdots+2+1) = 2^n+2^{n-1}+\cdots+2+1.
\]

Совершенно очевидно, что отбрасывание в правой части всех слагаемых, кроме первого, уменьшит сумму, поэтому \(2^{n+1}-1>2^n\). Но по предположению индукции \(2^n>n\), так что и \(2^{n+1}-1>n\), откуда вытекает требуемое \(2^{n+1}>n+1\). Индукционный переход удался!

Здесь интересно то, что человек углядел в индукционном переходе выражение, с которым ему оказалось легче работать и которое он сумел свести к сделанному предположению, из которого потом и получилось требуемое. Неожиданное и довольно изящное доказательство!