Математическая индукция, лошади и не только

[VoprosT]

Известный пример неправильного применения мат. индукции - доказательство того, что все лошади одного цвета. Ошибка в док-ве состоит в том, что шаг индукции не согласуется с базой - база верна при $n=1$, но при $n=2$ нет. Стало быть, доказывать надо для $n\geqslant3$, но доказать такую базу не представляется возможным. В связи с этим у меня следующий вопрос:
Задача - доказать, что $n^{n+1} > (n+1)^n$ при $n\geqslant3$. База $n=3$ проверяется, $n=4$ тоже. А вдруг на каком-то небольшом значении $n$ база неверна, как было с лошадьми? Или в этом и состоит отличие от задачи про лошадей - $n=4$ можно вывести из $n=3$, а там $n=2$ из $n=1$ не следовало?

[kotenok gav]

Нет, там проще. Или у нас есть база при $n\leq2$ и шаг при $n\geq3$ (и тогда база неверна), или у нас есть база при $n\leq1$ и шаг при $n\geq2$ (тогда шаг неверен).

[mihaild]

Где-то я эти слова (про "базу при разных $n$" в задаче о лошадях) уже видел. Видимо, есть какой-то источник, где это неудачно изложено. VoprosT, где вы прочитали, что

VoprosT в сообщении #1469381 писал(а):

Ошибка в док-ве состоит в том, что шаг индукции не согласуется с базой

?

Строго говоря, рассуждение по индукции должно иметь вид "если $P(1)$ [база] выполнено и для любого $n$ выполнено $P(n) \rightarrow P(n + 1)$ [шаг], то $P(n)$ выполнено для всех $n$" (ну либо начинаем с $0$ а не с $1$, в зависимости от того, считается ли $0$ натуральным числом в нашем разделе математики). И рассуждение про лошадей мимикрирует под эту схему: $P(1)$ - одна лошадь имеет один цвет, всё так. Но дальнейшее доказательство $P(n) \rightarrow P(n + 1)$ содержит ошибку - оно не проходит при $n = 1$.

[VoprosT]

mihaild в сообщении #1469386 писал(а):

Где-то я эти слова (про "базу при разных $n$" в задаче о лошадях) уже видел. Видимо, есть какой-то источник, где это неудачно изложено.

"Конкретная математика" за авторством Кнута, Паташника и Грэма (на русском языке), 34 страница, упражнение 1 и ответ к этому упражнению в конце книги

mihaild в сообщении #1469386 писал(а):

Строго говоря, рассуждение по индукции должно иметь вид "если $P(1)$ [база] выполнено и для любого $n$ выполнено $P(n) \rightarrow P(n + 1)$ [шаг], то $P(n)$ выполнено для всех $n$" (ну либо начинаем с $0$ а не с $1$, в зависимости от того, считается ли $0$ натуральным числом в нашем разделе математики). И рассуждение про лошадей мимикрирует под эту схему: $P(1)$ - одна лошадь имеет один цвет, всё так. Но дальнейшее доказательство $P(n) \rightarrow P(n + 1)$ содержит ошибку - оно не проходит при $n = 1$.

А когда мы осуществляем переход $n$ $\to$ $n+1$, то ограничение на $n$ (например, $n$\geqslant$10$) вылезет где-то в переходе в общем виде, и мы не сможем осуществить переход без того факта, что $n$\geqslant$10$? Хотя в лошадях этой проблемы не появилось, как тогда понять, что для каких-то $n$ шаг индукции не осуществим?

[eugensk]

VoprosT в сообщении #1469381 писал(а):

Задача - доказать, что $n^{n+1} > (n+1)^n$ при $n\geqslant3$
...
шаг индукции не согласуется с базой
...
как понять, что для каких-то $n$ шаг индукции не осуществим

Что с чем согласуется? надо сводить к первоисточнику.

Есть принцип индукции P(1) истинно, P(n) => P(n+1) истинно, тогда P(n) истинно для всех натуральных n.

Надо доказать какое-то утверждение не для всех натуральных. Тогда есть два пути:

- включить условие на n в это же утверждение,
- выразить n через переменную которая принимает уже все натуральные значения.

В нашем случае

доказываем утверждение
$n^{n+1} > (n+1)^n$ или $ n<3$ для $ n = 1,2,3,... $
- не очень то удобно

или доказываем утверждение
$n^{n+1} > (n+1)^n$ где $n = n'+2$ для $n' = 1,2,3,... $
- а тут сработает. Проверяем для n'=1, доказываем => . Получаем что истинно для всех n', значит, для всех n>=3.

Всё, ничего согласовыать не надо.

[mihaild]

VoprosT в сообщении #1469393 писал(а):

"Конкретная математика"

Там я вижу формулировку упражнения, а в ответах - "доказательство безупречно за исключением случая $n = 2$". Про "согласование шага с базой" там ничего нет.

VoprosT в сообщении #1469393 писал(а):

А когда мы осуществляем переход $n$ $\to$ $n+1$, то ограничение на $n$ (например, $n$\geqslant$10$) вылезет где-то в переходе в общем виде, и мы не сможем осуществить переход без того факта, что $n$\geqslant$10$, верно?

Да.
Тут есть немного тонкий момент - у нас могут быть два "разных" рассуждения для $n < 10$ и для $n \geqslant 10$. Например можно непосредственно проверить утверждение при $n \leqslant 10$ (и этого достаточно для перехода при $n < 10$ - мы непосредственно доказали $P(n + 1)$ для таких случаев, этого достаточно для импликации), а дальше записать переход. Но и такое рассуждение можно записать в общую схему эти две части вместе доказывают, что $P(n) \rightarrow P(n + 1)$, а нам нужно именно это, как именно сам переход доказывается для рассуждения по индукции не важно.

[VoprosT]

mihaild в сообщении #1469399 писал(а):

VoprosT в сообщении #1469393 писал(а):

"Конкретная математика"

Там я вижу формулировку упражнения, а в ответах - "доказательство безупречно за исключением случая $n = 2$". Про "согласование шага с базой" там ничего нет.

Поправочка: про "согласование с базой" вычитал на Вики в попытках разобраться, к слову, на Вики не разобрался: https://ru.wikipedia.org/wiki/%D0%94%D0 ... 0%B5%D0%B9

[mihaild]

VoprosT в сообщении #1469405 писал(а):

про "согласование с базой" вычитал на Вики

Ага, спасибо. Убрал оттуда эти странные слова.

[VoprosT]

Тогда вот такое уточнение про то, что в обосновании должна вылезти необходимость в $n$\geqslant$k$.

Антидемидович, Том 1, 46 пример (как раз таки пример, который вместе с лошадьми в первом сообщении):

Неравенство $n^{n+1}>(n+1)^n$ умножается на $\frac{(n+1)^{n+2}}{n^{n+1}}$, получается $(n+1)^{n+2}>\frac{(n+1)^{2(n+1)}}{n^{n+1}}$

И $\frac{(n+1)^{2(n+1)}}{n^{n+1}}$$ $=$ $(\frac{n^2+2n+1}{n})^{n+1}$ $>$ $(n+2)^{n+1}$

Где здесь понадобилось $n\geqslant3$? Или может док-во некорректно?

[Sender]

VoprosT в сообщении #1469415 писал(а):

Где здесь понадобилось $n\geqslant3$?

А какое значение $n$ вы собираетесь брать для базы индукции?

[VoprosT]

Sender в сообщении #1469424 писал(а):

VoprosT в сообщении #1469415 писал(а):

Где здесь понадобилось $n\geqslant3$?

А какое значение $n$ вы собираетесь брать для базы индукции?

$n=3$

[mihaild]

VoprosT в сообщении #1469427 писал(а):

$n=3$

А какое в точности утверждение вы доказываете по индукции? Оно должно иметь вид "для любого $n$ что-то там".

[VoprosT]

mihaild в сообщении #1469429 писал(а):

VoprosT в сообщении #1469427 писал(а):

$n=3$

А какое в точности утверждение вы доказываете по индукции? Оно должно иметь вид "для любого $n$ что-то там".

$n^{n+1}>(n+1)^n$

[mihaild]

VoprosT в сообщении #1469431 писал(а):

$n^{n+1}>(n+1)^n$

Это утверждение у вас доказать не получится, потому что оно неверно (подставьте $n = 1$).

[VoprosT]

mihaild в сообщении #1469433 писал(а):

VoprosT в сообщении #1469431 писал(а):

$n^{n+1}>(n+1)^n$

Это утверждение у вас доказать не получится, потому что оно неверно (подставьте $n = 1$).

Я как раз про то, что оно верно при $n$\geqslant$3$, но при переходе $n$$\to$$n+1$ это(условие) вроде как и не используется, но в сообщении чуть выше вы писали (про $n$\geqslant$10$), что это должно сыграть