2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Мат. индукция (на примере)
Сообщение24.06.2018, 18:26 


12/11/11
88
Не могли бы вы проверить, правильно ли я использую принцип (метод) математической индукции при доказательстве теоремы? Вот его определение:
Пусть $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$ не во всё множество натуральных чисел, а в упомянутое мною подмножество?

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 18:41 


21/05/16
4292
Аделаида
SteelRend в сообщении #1322312 писал(а):
Полностью правильно или есть недочёты/ошибки?

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

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

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

Да.

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 18:45 


12/11/11
88
kotenok gav в сообщении #1322323 писал(а):
М не подмножество N.

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

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 18:47 


21/05/16
4292
Аделаида
SteelRend в сообщении #1322326 писал(а):
что $n \in N$

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

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 18:49 
Заслуженный участник


11/05/08
32166
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$ножества сдвинуть нумерацию на единичку, подогнав под стандарт, но это никому не нужная ловля блох.

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 19:04 


12/11/11
88
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$

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

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 19:13 
Заслуженный участник


11/05/08
32166
SteelRend в сообщении #1322339 писал(а):
а что насчёт моего
Цитата:
Пусть $n \in M$, т.е. для любого натурального $i \leq n$ выполнено $2^i > i$

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

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 19:32 
Заслуженный участник


31/12/15
922
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$ (состоит из натуральных чисел с некоторым свойством).

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 19:58 


12/11/11
88
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$ состоит только из натуральных чисел.

 Профиль  
                  
 
 Re: Мат. индукция (на примере)
Сообщение24.06.2018, 20:21 
Заслуженный участник


31/12/15
922
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$ было бы составным"?

Да.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group