Мат. индукция (на примере)

[SteelRend]

Не могли бы вы проверить, правильно ли я использую принцип (метод) математической индукции при доказательстве теоремы? Вот его определение:
Пусть $M$ - такое множество, что:
1) $1 \in M$
2) $\forall n \in N$ из того, что $n \in M \Longrightarrow (n+1) \in M$. Тогда $M \supset N$. В частности, если $M \subset N$, то $M = N$.

Применяя метод мат. индукции, нужно доказать, что для $2^n > n$, $n \geq 1$.
Пусть $M$ - множество таких чисел $n \in N$, что $2^n > n$.
Проверяем $1 \in M$: $2^1 = 2 > 1$ - неравенство выполняется, т.е. мы доказали, что $1 \in M$.
Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$ (тут я на самом деле не знаю как правильно говорить, вряд ли я могу сказать "Пусть для любого натурального $n$ выполнено $2^n > n$")
Проверяем принадлежность $(n + 1) \in M$:
$2^n > n$ (предположение индукции)
$2 \cdot 2^n > 2 \cdot n$ (свойства неравенств; выполняется потому что выполнено предыдущее)
Теперь подробнее: $2 \cdot 2^n = 2^{n+1} > 2 \cdot n = n + n > n + 1$.
Т.е. $2^{n+1} > n+1$ удовлетворяет неравенству, т.е. $(n+1) \in M$.
Отсюда $M \supset N$ и, поскольку $M \subset N$ (не знаю, правда, почему; по-видимому, я должен здесь это сказать), то $M = N$ и неравенство выполняется для всех натуральных чисел.

Полностью правильно или есть недочёты/ошибки?

Ещё вопрос. Пусть мат. индукцией пытаемся доказать, что $4^n - 1$ составное число при $n > 1$. Тут мы не должны доказывать, что $1 \in M$ (и не можем этого сделать). Правильно ли я понимаю, что в этом случае речь идёт не о всём множестве $N$, а о его (неограниченном сверху) подмножестве, имеющем по определению первый элемент, и тогда мы базу индукции доказываем для этого первого элемента (вернее, мы имеем право это делать, несмотря на то как у меня записан принцип мат. индукции), т.е. для $n = 2$, и доказываем включение множества $M$ не во всё множество натуральных чисел, а в упомянутое мною подмножество?

[kotenok gav]

SteelRend в сообщении #1322312 писал(а):

Полностью правильно или есть недочёты/ошибки?

М не подмножество N. Но вам хватает того, что N подмножество М.

-- 25 июн 2018, 01:12 --

SteelRend в сообщении #1322312 писал(а):

Правильно ли я понимаю, что в этом случае речь идёт не о всём множестве $N$, а о его (неограниченном сверху) подмножестве, имеющем по определению первый элемент, и тогда мы базу индукции доказываем для этого первого элемента (вернее, мы имеем право это делать, не смотря на то как у меня записан принцип мат. индукции), т.е. для $n = 2$, и доказываем включение множества $M$ не во всё множество натуральных чисел, а в упомянутое мною подмножество?

Да.

[SteelRend]

kotenok gav в сообщении #1322323 писал(а):

М не подмножество N.

Почему? Я же сказал, "пусть $M$ - множество таких чисел $n \in N$, что $2^n > n$", т.е. я говорю, что не исключаю того, что какие-то числа $n$ этому неравеству могут удовлетворять. Но при этом, даже если таких чисел - пустое множество, то всё равно $M \subset N$. Или это Вы говорите об определении принципа мат. индукции, который у меня записан неверно?

[kotenok gav]

SteelRend в сообщении #1322326 писал(а):

что $n \in N$

Не заметил, извините.

[ewert]

SteelRend в сообщении #1322312 писал(а):

Полностью правильно или есть недочёты/ошибки?

Почти правильно -- есть формальная ошибка: на самом деле $n+n\geqslant n+1$. Но это ничему не мешает.

Недочётом же можно считать упоминание какого-то там множества $M$. Нормальные люди формулируют этот метод не на языке множеств, а на языке высказываний: если некоторое высказывание $P(n)$ истинно для некоторого начального $n=n_0$ (база индукции) и если из $P(n)$ следует $P(n+1)$ (индукционный переход) то $P(n)$ истинно при любом $n\geqslant n_0$. Это, конечно, то же самое, но не в пример удобнее. Если же вас из какого-то принципа заставляют именно мучиться с $M$ножествами, то могу только посочувствовать.

База же индукции может быть какой угодно. В частности, для $4^n-1$ утверждение верно только начиная с $n=2$ -- соответственно, это и будет базой. Конечно, можно в описании $M$ножества сдвинуть нумерацию на единичку, подогнав под стандарт, но это никому не нужная ловля блох.

[SteelRend]

ewert
а что насчёт моего

Цитата:

Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$

?
Получается, корректно именно так говорить? Вернее, говорить надо "...для любого натурального $1 \leq i \leq n$ выполнено $2^i > i$ (хотя это лишь несущественное уточнение).

А это правильно

Цитата:

"пусть $M$ - множество таких чисел $n \in N$, что $2^n > n$", т.е. я говорю, что не исключаю того, что какие-то числа $n$ этому неравеству могут удовлетворять. Но при этом, даже если таких чисел - пустое множество, то всё равно $M \subset N$

?
Или это лишь мои фантазии на тему того, как нужно интерпретировать приведённое определение метода мат. индукции?

[ewert]

SteelRend в сообщении #1322339 писал(а):

а что насчёт моего

Цитата:

Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$

Не обратил внимания, т.к. это тоже вариант метода матиндукции. Но, во-первых, не тот, что у Вас сформулирован в стартовом посте. А во-вторых, Вам он вовсе и не нужен -- предположить достаточно, что просто $2^n>n$.

[george66]

SteelRend в сообщении #1322312 писал(а):

Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$ (тут я на самом деле не знаю как правильно говорить, вряд ли я могу сказать "Пусть для любого натурального $n$ выполнено $2^n > n$")

Тут надо сказать "пусть для некоторого натурального $n$ выполнено $n\in M$, то есть $2^n>n$. Докажем, что $n+1\in M$"
Из этого по правилам логики следует $\forall n (n\in M\Rightarrow n+1\in M)$, поскольку $n$ можно брать любое.

-- 24.06.2018, 19:39 --

SteelRend в сообщении #1322312 писал(а):

Ещё вопрос. Пусть мат. индукцией пытаемся доказать, что $4^n - 1$ составное число при $n > 1$. Тут мы не должны доказывать, что $1 \in M$ (и не можем этого сделать). Правильно ли я понимаю, что в этом случае речь идёт не о всём множестве $N$, а о его (неограниченном сверху) подмножестве, имеющем по определению первый элемент, и тогда мы базу индукции доказываем для этого первого элемента (вернее, мы имеем право это делать, несмотря на то как у меня записан принцип мат. индукции), т.е. для $n = 2$, и доказываем включение множества $M$ не во всё множество натуральных чисел, а в упомянутое мною подмножество?

Мы доказываем свойство "$n>1\Rightarrow 4^n-1$ составное число". Множество чисел с таким свойством содержит $1$ (потому что "$1>1\Rightarrow 4^1-1$ составное", из неверной посылки следует что угодно).

-- 24.06.2018, 19:44 --

SteelRend в сообщении #1322312 писал(а):

Пусть $M$ - множество таких чисел $n \in N$, что $2^n > n$.

Отсюда $M \supset N$ и, поскольку $M \subset N$ (не знаю, правда, почему; по-видимому, я должен здесь это сказать), то $M = N$ и неравенство выполняется для всех натуральных чисел.

По определению $M$ является подмножеством $N$ (состоит из натуральных чисел с некоторым свойством).

[SteelRend]

george66 в сообщении #1322354 писал(а):

SteelRend в сообщении #1322312 писал(а):

Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$ (тут я на самом деле не знаю как правильно говорить, вряд ли я могу сказать "Пусть для любого натурального $n$ выполнено $2^n > n$")

Тут надо сказать "пусть для некоторого натурального $n$ выполнено $n\in M$, то есть $2^n>n$. Докажем, что $n+1\in M$"
Из этого по правилам логики следует $\forall n (n\in M\Rightarrow n+1\in M)$, поскольку $n$ можно брать любое.

Что есть тогда предположение индукции $2^n > n$? Это истинное утверждение, что для произвольного $n$ выполнено $2^n > n$, или лишь предположение "пусть $2^n > n$, где $n \in N$ выбирается произвольно, тогда..."

Цитата:

SteelRend в сообщении #1322312 писал(а):

Ещё вопрос. Пусть мат. индукцией пытаемся доказать, что $4^n - 1$ составное число при $n > 1$. Тут мы не должны доказывать, что $1 \in M$ (и не можем этого сделать). Правильно ли я понимаю, что в этом случае речь идёт не о всём множестве $N$, а о его (неограниченном сверху) подмножестве, имеющем по определению первый элемент, и тогда мы базу индукции доказываем для этого первого элемента (вернее, мы имеем право это делать, несмотря на то как у меня записан принцип мат. индукции), т.е. для $n = 2$, и доказываем включение множества $M$ не во всё множество натуральных чисел, а в упомянутое мною подмножество?

Мы доказываем свойство "$n>1\Rightarrow 4^n-1$ составное число". Множество чисел с таким свойством содержит $1$ (потому что "$1>1\Rightarrow 4^1-1$ составное", из неверной посылки следует что угодно).

Т.е. что-то вроде "если бы выполнялось $1 > 1$, то число $4^1 - 1 = 3$ было бы составным"?

Цитата:

По определению $M$ является подмножеством $N$ (состоит из натуральных чисел с некоторым свойством).

Я понял, это потому, что мы рассматриваем $M$ как состоящее только из натуральных чисел (принадлежность множеству $M$ других чисел мы не допускаем -- таковы условия задачи). В нём нет, например, числа $1.5$, поэтому мы можем, не опасаясь возникновения противоречий, считать, что $M \subset N$. Это замечание в определении принципа мат. индукции дано для полноты и строгости, но всегда по смыслу (в тех примерах, что я встречал) $M$ состоит только из натуральных чисел.

[george66]

SteelRend в сообщении #1322361 писал(а):

Что есть тогда предположение индукции $2^n > n$? Это истинное утверждение, что для произвольного $n$ выполнено $2^n > n$, или лишь предположение "пусть $2^n > n$, где $n \in N$ выбирается произвольно, тогда..."

Второе.

-- 24.06.2018, 20:24 --

SteelRend в сообщении #1322361 писал(а):

Т.е. что-то вроде "если бы выполнялось $1 > 1$, то число $4^1 - 1 = 3$ было бы составным"?

Да.