Математическая индукция

[Gts]

TOTAL в сообщении #735145 писал(а):

Gts в сообщении #735139 писал(а):

Цитата:

В очередь за картошкой один за другим стоят люди.
1) Каким-то способом доказали (проверили), что самый первый в очереди - мужчина.
2) Доказали также, что в любом месте очереди за мужчиной может стоять только мужчина.

Можно ли сделать вывод о том, что в очереди стоят одни только мужчины? А?

Да. Тут всё просто. Мне тут не нужно знать метод индукции. Из самих утверждений следует, что очередь состоит из одних мужчин.

Как это следует, ведь Вы не проверяли каждого?

Исходя из слов

Цитата:

в любом месте очереди за мужчиной может стоять только мужчина

и это утверждение доказано.

[svv]

А вдруг первой (а может, и второй, и третьей...) стоит женщина? Тогда ведь условие "за мужчиной -- мужчина" не нарушается!

[iifat]

lena7 в сообщении #735031 писал(а):

А правдоподобное рассуждение -- если ты можешь подняться на первую ступеньку и с каждой ступеньки можешь подняться на следующую, то ты можешь подняться на любую ступеньку

Никакое это не правдоподобное утверждение. Это — доказательство методом математической индукции.
Правдоподобное утверждение — это, например, "я проверил числа от 0 до 999. Все они меньше тысячи. Резонно предположить, что все натуральные числа меньше тысячи".

[Gts]

Цитата:

А вдруг первой (а может, и второй, и третьей...) стоит женщина? Тогда ведь условие "за мужчиной -- мужчина" не нарушается!

Написано: "доказали (проверили), что самый первый в очереди - мужчина." Из этого следует, что на первом месте женщина стоять не может.
Далее, пусть второй стоит женщина, но тогда это противоречит условию, что за мужчиной стоит только мужчина.

[TOTAL]

Gts в сообщении #735286 писал(а):

Цитата:

А вдруг первой (а может, и второй, и третьей...) стоит женщина? Тогда ведь условие "за мужчиной -- мужчина" не нарушается!

Написано: "доказали (проверили), что самый первый в очереди - мужчина." Из этого следует, что на первом месте женщина стоять не может.
Далее, пусть второй стоит женщина, но тогда это противоречит условию, что за мужчиной стоит только мужчина.

1) Первое утверждение верно (т.к. просто проверили)
2) Доказали, что за верным утверждением может стоять только верное утверждение

Могут ли в очереди из утверждений быть ложные утверждения?

[Gts]

Цитата:

Могут ли в очереди из утверждений быть ложные утверждения?

Нет, в такой очереди ложных утверждений не будет.

[TOTAL]

Gts в сообщении #735297 писал(а):

Цитата:

Могут ли в очереди из утверждений быть ложные утверждения?

Нет, в такой очереди ложных утверждений не будет.

Это и есть метод математической индукции.

[Gts]

Я ещё что-то недопонимаю.

Цитата:

1) Каким-то способом доказали (проверили), что самый первый в очереди - мужчина.
2) Доказали также, что в любом месте очереди за мужчиной может стоять только мужчина.

А для использования математической индукции мне самому нужно доказывать пункт 2?

[Otta]

Да.

[Gts]

Цитата:

Пусть, например, требуется доказать для любого натурального (целого положительного) числа $n$ формулу:
$ 1 + 3 + 5 + ... + (2n - 1) = n^2 $ (1)

При $n = 1$ эта формула даёт $1 = 1^2$. Чтобы доказать правильность формулы при любом $n$, допускают, что её уже удалось доказать для некоторого определённого числа $N$, то есть предполагают, что
$ 1 + 3 + 5 + ... + (2N - 1) = N^2. $ (2)

Далее, опираясь на сделанное допущение, пытаются доказать правильность формулы (1) для числа на единицу большего, то есть для $n = N + 1$. В данном случае достаточно присоединить к сумме в левой части равенства (2) ещё одно слагаемое: $(2N + 1)$; тогда и правая часть равенства должна увеличиться на $(2N +1)$ и, следовательно,
$1 + 3 + 5 + ... + (2N - 1) + (2N + 1) = N^2 + (2N + 1) = (N + 1)^2$.

Но тот же результат получится, если в формуле (1) заменить $n$ на $N + 1$.
Итак, из справедливости формулы (1) при $n = N $вытекает (каково бы ни было $N$) её правильность и при $n = N + 1$. Но при$ n = 1$ формула (1) верна, следовательно, она верна также и при $n = 2 = 1 + 1, 3 = 2 + 1, 4 = 3 + 1, 5 = 4 + 1$ и так далее. Так как последовательным прибавлением единицы можно получить (начиная с единицы) любое натуральное число, то формула (1) действительно верна при любом натуральном числе $ n$.

Это рассуждение верно?
Если верно, то где доказано, что $ 1 + 3 + 5 + ... + (2N - 1) = N^2 $ является истинным утверждением? Я не понимаю этого перехода от $n$ к $N$.

[Otta]

Gts в сообщении #735432 писал(а):

Это рассуждение верно?
Если верно, то где доказано, что $ 1 + 3 + 5 + ... + (2N - 1) = N^2 $ является истинным утверждением? Я не понимаю этого перехода от $n$ к $N$.

Нигде не доказано. Читайте внимательно.

Цитата:

Чтобы доказать правильность формулы при любом $n$, допускают, что её уже удалось доказать для некоторого определённого числа $N$, то есть предполагают, что
$ 1 + 3 + 5 + ... + (2N - 1) = N^2. $ (2)

Рассуждение же (процитированное Вами) в целом верно, но кривовато изложено.

[Gts]

Так а я о чём! Специально же выделил. Почему я имею право применять такой ход рассуждений, если $P_n$ ($ 1 + 3 + 5 + ... + (2N - 1) = N^2 $) является лишь предположением?

Подобная формулировку я встретил в книге "Что такое математика" Куранта. Оттуда и зацепился за это "предположение".

[Otta]

Gts
Вы различайте предположение индукции и шаг индукции.
Предположение ни к чему не обязывает. Обязывает, когда, сделав предположение, удается сделать шаг.

Давайте на примере TOTAL, раз он оказался удачным.

TOTAL в сообщении #735296 писал(а):

1) Первое утверждение верно (т.к. просто проверили)
2) Доказали, что за верным утверждением может стоять только верное утверждение

Могут ли в очереди из утверждений быть ложные утверждения?

Вы выяснили, что нет, не могут.

А теперь сравните с тем, что предлагаете Вы.

Пусть
1) Первое утверждение в очереди верно.
2) Предположим, что еще некоторое утверждение в очереди верно.

Следует ли отсюда, что все утверждения в очереди верны? Да? Нет?

Видите разницу?

[Gts]

Предположение индукции - это $ 1 + 3 + 5 + ... + (2N - 1) = N^2$.
Шаг индукции - это $1 + 3 + 5 + ... + (2N - 1) + (2N + 1) = N^2 + (2N + 1) = (N + 1)^2$.
Верно?

Цитата:

Обязывает, когда, сделав предположение, удается сделать шаг.

Что Вы подразумеваете под словом "обязывает"? Мне не понятно это предложение.

Цитата:

Пусть
1) Первое утверждение в очереди верно.
2) Предположим, что еще некоторое утверждение в очереди верно.

Следует ли отсюда, что все утверждения в очереди верны? Да? Нет?

Нет, из этих двух утверждений не следует, что все утверждения в очереди верны. Я вижу разницу.
Но я вижу именно вот эти два предположения в цитате. Там проверили базу индукции. Сделали предположение, от него сделали переход к следом стоящему утверждению. Грубо говоря, увидели, что полученное утверждение совпадает с заданным плюс 1. Ч.т.д.
Где там доказывается "Доказали, что за верным утверждением может стоять только верное утверждение"? Там нигде не подставляются конкретные значения из ряда суммы и не проверяется ни предположение индукции, ни шаг индукции.

[TOTAL]

Gts в сообщении #735448 писал(а):

Где там доказывается "Доказали, что за верным утверждением может стоять только верное утверждение"?

Вот где

Цитата:

Далее, опираясь на сделанное допущение, пытаются доказать правильность формулы (1) для числа на единицу большего, то есть для $n = N + 1$. В данном случае достаточно присоединить к сумме в левой части равенства (2) ещё одно слагаемое: $(2N + 1)$; тогда и правая часть равенства должна увеличиться на $(2N +1)$ и, следовательно,
$1 + 3 + 5 + ... + (2N - 1) + (2N + 1) = N^2 + (2N + 1) = (N + 1)^2$.

Но тот же результат получится, если в формуле (1) заменить $n$ на $N + 1$.
Итак, из справедливости формулы (1) при $n = N $вытекает (каково бы ни было $N$) её правильность и при $n = N + 1$.