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

[provincialka]

А что, вы можете доказать по отдельности для каждого $n$? Их вроде бесконечное число.

[Otta]

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

Про отличие высказываний от описания объекта и описание ряда с помощью рекуррентной формулы я понял.

Проясните, пожалуйста, ещё индукционный переход. У меня ещё нет понимания этого момента.

Цитата:

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: $P_1, P_2, P_3,\dots,P_n, P_{n+1},...$
Допустим, что:
1. Установлено, что $P_1$ верно. (Это утверждение называется базой индукции.)
2. Для любого $n$ доказано, что если верно $P_n$ , то верно $P_{n+1}$ . (Это утверждение называется индукционным переходом.)
Тогда все утверждения нашей последовательности верны.

Ну, поехали. Установлено, что $P_1$ верно (верно наше утверждение $P_n$ при $n=1$) - п.1
Из п.2 тогда следует, что при $n=2$ оно тоже верно.
Но тогда из п.2 следует, что при $n=3$ оно тоже верно.
Но тогда... и т.д.

Значит, верно при всех $n$. Значит, к п.1 действительно достаточно доказать п. 2.
Что непонятно?

[Gts]

Кажется, я смог более полно сформулировал свою мысль.

Есть ряд $S_n = 1+3+5+7+\dots + n = \frac {n(n+1)} {2} $. То есть это сумма нечётных чисел, но сделана ошибка в формуле общего члена и в формуле суммы. База индукции $S_1 = 1$. Делаем предположение, что наша гипотеза верна для $n$, поэтому мы докажем, что она верна и для $n+1$ и получаем $S_{n+1} = \frac {(n+2)(n+1)} {2}$, что является истинной, так как если в исходную формулу суммы подставить $n+1$, то мы получим это же выражение. Таким образом мы делаем неверное заключение, что эта формула суммы для данного ряда истинное утверждение.
Вопрос: как выходить из ситуации, когда сделаны подобные ошибка в утверждении для $P_n$ и для $S_n$?

[mihailm]

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

... и получаем $S_{n+1} = \frac {(n+2)(n+1)} {2}$, что является истинной, так как если в исходную формулу суммы подставить $n+1$, то мы получим это же выражение...

Вы пока так и не поняли метода матиндукции.
Нельзя подставлять в формулу $n+1$

[TOTAL]

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

Делаем предположение, что наша гипотеза верна для $n$, поэтому мы докажем, что она верна и для $n+1$

Одним лишь деланием предположения о том, что гипотеза верна для $n$, не докажешь, что она верна и для $n+1$. Это понятно?

[Otta]

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

Делаем предположение, что наша гипотеза верна для $n$ , поэтому мы докажем, что она верна и для $n+1$

"Поэтому" - не докажем. Мы должны доказать, что если она верна для $n$, то верна и для $n+1$. Если Вы это попытаетесь проделать с Вашей суммой, у Вас не получится. Просто так справедливость утверждения для $n+1$ из справедливости утверждения для $n$ не следует.

Разрешая себе подставлять в формулу $n+1$ и на этом основании объявлять ее истинной - логическая ошибка. Наоборот, подставлять можно в предположении истинности. А Вам на этом шаге ее нужно обосновывать.

[Gts]

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

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

Делаем предположение, что наша гипотеза верна для $n$, поэтому мы докажем, что она верна и для $n+1$

Одним лишь деланием предположения о том, что гипотеза верна для $n$, не докажешь, что она верна и для $n+1$. Это понятно?

Это вот меня и смущает. И я в примерах не вижу, чтобы гипотеза для $n$ доказывалась.


Пример 1
Здесь делается предположение, что $P_n$ верно, но его не доказывают. Потом к обеим частях равенства добавляют $P_{n+1}$ и в итоге получают такую же формулу, какая получается, если в исходную формулу подставить $n+1$

Пример 2

Цитата:

... Чтобы доказать правильность формулы при любом n, допускают, что её уже удалось доказать для некоторого определённого числа N, то есть предполагают...(дальше в исходном утверждении $n$ заменяют на $N$ и всё)

И тут не доказывают верность $P_n$.

Цитата:

Мы должны доказать, что если она верна для $n$, то верна и для $n+1$

А почему ни в одном примере выше не доказывается, что гипотеза для $n$ верна, а сразу предполагается её истинность?

[TOTAL]

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

Потом к ни в одном примере выше не доказывается, что гипотеза для $n$ верна, а сразу предполагается её истинность?

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

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

[svv]

Правдоподобное обоснование метода математической индукции.

Пусть мы доказали
Базу: $P_1$
Шаг: $(\forall n\in \mathbb N) P_n\Rightarrow P_{n+1}$

Возьмём некоторое $n$. Докажем от противного, что $P_n$ истинно.
Пусть $P_n$ ложно.
Тогда существует минимальное $k\in\mathbb N$, при котором $P_k$ ложно (*).
$k$ не может быть равным $1$, это противоречит $P_1$. Значит, $k>1$, и можно рассмотреть истинность $P_{k-1}$.
$P_{k-1}$ не может быть ложно, потому что это противоречит (*).
$P_{k-1}$ не может быть истинно, так как из доказанного шага индукции следует, что $P_{k-1}\Rightarrow P_k$, а тогда и $P_k$ истинно, что опять противоречит (*).
Противоречие означает, что $P_n$ истинно.

[TOTAL]

svv в сообщении #735028 писал(а):

Правдоподобное обоснование метода математической индукции.

Обоснование чего, какого метода? Автор не понимает, в чем заключается метод.

[lena7]

(Оффтоп)

svv в сообщении #735028 писал(а):

Правдоподобное обоснование метода математической индукции.

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

[svv]

Я подумал, что раз Gts всё время беспокоится, а где же мы доказываем собственно $P_n$, то -- вот, пожалуйста, можно и доказать. Вероятно, метод на уровне "делай так" он понимает, но это в его представлении не есть доказательство. Всё, что мы имеем, это доказанные базу и шаг, и отсюда как бы ничего больше не следует. В частности, не следует истинность $P_n$ для произвольного $n\in\mathbb N$. Иными словами, Gts считает, что метод нуждается в обосновании.

[Otta]

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

Неправда, доказывается

TOTAL,

(Оффтоп)

ну конечно, доказывается для базы. Ну знаю я. Я ж пыталась с человечего на птичий. А в остальном, со всем что Вы сказали и еще только собираетесь сказать, я заранее согласна. Поверьте на слово, я знаю метод математической индукции.

[Gts]

svv, я встречал доказательство метода, но мне пока в него рано соваться, слишком много нового.

Цитата:

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

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

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

Цитата:

Неправда, доказывается (обычно для $n=1$).

А зачем там пишут слова "допустим, что $P_n$ верно"?
Да и в моём понимании $n=1$, это частный случай, и экстраполировать его на все случаи до $n$ как-то странно...


$S_n = 1+3+5+7+\dots + n = \frac {n(n+1)} {2} $. Гипотеза для $n=1$ верна. Гипотеза $S_{n+1} = \frac {(n+1)(n+2)} {2}$ не верна, так как если мы подставим туда $n=1$, то получим $S_{n+1} = 3$, а на самом деле сумма должна быть $4$ для второго члена суммы. Здесь я все утверждения обосновал подстановкой конкретных значений. Вопрос: как в примерах по ссылке проверяют утверждение $P_{n+1}$?

[TOTAL]

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

Цитата:

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

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

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

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