Метод математической индукции доказательство: Математическое Бюро. Страница 404

Принцип правильного порядка: Каждое непустое множество положительных целых чисел содержит наименьший элемент.

Справедливость математической индукции в этом контексте, когда мы используем WOP для доказательства достоверности математической индукции, устанавливается с помощью доказательства от противного. Это доказательство будет содержать несколько «шагов» или «частей». Прежде чем приводить все шаги доказательства математической индукции, может быть полезно переформулировать определение метода доказательства в терминах обозначений, которые будут использоваться на протяжении всей последовательности шагов объяснения (для согласованности и облегчения понимания):

Переформулированный принцип математической индукции: Для некоторого фиксированного целого числа $1$ и для каждого целого числа $n\geq 1$ пусть $S(n)$ — утверждение, содержащее $n$. Если

1. $S(1)$ верно, а
2. для любого целого числа $k\geq 1, S(k)\to S(k+1)$,

, то для всех $n\geq 1$ верно утверждение $S(n)$.

Пусть 1 и 2 выше обозначены $(\dagger)$ и $(\dagger\dagger)$ соответственно.

Шаги доказательства того, что математическая индукция является следствием ВОП:

1. Предположим, что $S(1)$ истинно и что предложение $S(k) \rightarrow S(k+1)$ истинно для всех натуральных чисел $k$, т. е. где $( \dagger)$ и $(\dagger\dagger)$ выполняются, как указано выше.

2. Цель состоит в том, чтобы проверить, истинно ли $S(n)$ для всех $n \geq 1$, если $S(1)$ и $S(k) \rightarrow S(k+1)$ истинны. . Утверждение математической индукции выше показывает, что $S(n)$ будет логически следовать, если $S(1)$ и $S(k) \rightarrow S(k+1)$ истинны, но не $S(n)$ действительно следует, если $(\dagger)$ и $(\dagger\dagger)$ верны? Если да, то математическая индукция является допустимым методом доказательства. Если нет, то это просто мусор.

3. Мы скептики и думаем, что математическая индукция — обман (подсказка: вот-вот произойдет доказательство от противного). Наш скептицизм заставляет нас предположить, что существует по крайней мере одно положительное целое число, для которого $S(n)$ ложно [имейте в виду, что мы предполагаем, что $(\dagger)$ и $(\dagger\dagger)$ истинны, хотя мы спорим о том, действительно ли $S(n)$ следует из их истинности]. Наверняка существует хотя бы одно натуральное число, для которого $S(n)$ ложно, даже если $S(1)$ и $S(k) \rightarrow S(k+1)$ истинны.

4. Пусть $\mathcal{P}$ обозначает множество всех натуральных чисел, для которых $S(n)$ ложно. Этот набор пуст? Мы думаем, что нет — в конце концов, мы предполагаем, что существует по крайней мере одно натуральное число, скажем, $\ell$, для которого $S(n)$ ложно; то есть предположение состоит в том, что $S(\ell)$ ложно, где $\ell \in \mathcal{P}$. Существуют ли другие положительные целые числа в $\mathcal{P}$? Возможно, но мы пока не можем сказать наверняка. Однако мы можем с уверенностью заявить, что $\mathcal{P}$ имеет наименьший элемент по принципу правильного порядка. Пусть наименьший элемент $\mathcal{P}$ равен $\ell$ без ограничения общности.

5. Поскольку $S(1)$ истинно, мы знаем, что $\ell \neq 1$, а поскольку $\ell$ положительно и больше $1$, мы также знаем, что $\ell -1$ должно быть положительное число. Более того, поскольку $\ell-1$ меньше, чем $\ell$, должно быть ясно, что $\ell-1$ не может быть в $\mathcal{P}$ [это потому, что $\ell$ — наименьший элемент в $\mathcal{P}$, что означает, что любое меньшее натуральное число не может быть в $\mathcal{P}$]. Условно у нас есть это $\ell \in \mathcal{P}$ и $(\ell — 1) \notin \mathcal{P}$. Что это значит? Поскольку $(\ell — 1) \notin \mathcal{P}$ и $\ell -1$ — натуральное число, а $\mathcal{P}$ — множество все целых положительных числа, для которых $S(n)$ ложно, должно быть, что $S(\ell-1)$ истинно.

6. Наконец, вспомним, что мы утверждали, что $(\dagger\dagger)$ было правдой; то есть $S(k) \rightarrow S(k+1)$ верно для любого целого числа $k \geq 1$. Поскольку $\ell$ и $\ell -1$ оба являются положительными целыми числами, мы можем положить $k = \ell -1$ и $k+1 = \ell$. Подставив эти значения в импликацию, которую мы считаем истинной, мы получим, что $S(\ell-1) \rightarrow S(\ell)$. Теперь вы видите проблему (и, следовательно, вывод доказательства от противного)?

7. Предполагая, что $(\dagger)$ и $(\dagger\dagger)$ верны, а также предположив, что $S(n)$ ложно для некоторого положительного целого числа $\ell$, мы сделали вывод, проделав серию шагов, что $S(\ell-1) \rightarrow S(\ell)$ [по $(\dagger\dagger)$, где $k = \ell -1$ и $k+1 = \ell$]. Что с этим не так? Просто рассмотрите следующие три утверждения, которые встречаются в доказательстве:

   • $S(\ell-1)\to S(\ell)\qquad$ [ Верно —по предположению $(\dagger\dagger)$] 9+}$]
   • $S(\ell-1)\qquad$ [ Истинно — по принципу упорядочения]

   Теперь логическая проблема должна стать очевидной. Мы знаем, что $S(\ell-1) \rightarrow S(\ell)$ истинно из нашего исходного предположения, но это следствие не может быть истинным, если $S(\ell)$ ложно. Почему? Потому что импликация формы $p \rightarrow q$ ложна только тогда, когда гипотеза $p$ верна, а вывод $q$ ложен. В нашем собственном случае, поскольку $S(\ell-1)$ истинно, импликация $S(\ell-1) \rightarrow S(\ell)$ истинна только тогда, когда также истинно $S(\ell)$ , таким образом противоречит выбору $\ell$. Следовательно, $S(n)$ должно быть истинным для каждого натурального числа $n$.

Приложение: Другим студентам, изучающим курсы дискретной математики, может быть интересно, что доказанная выше форма индукции (часто называемая просто «индукцией») на самом деле эквивалентна как сильной индукции , так и WOP . Это может показаться удивительным, но для интересующихся читателей есть хорошая статья об эквивалентности трех вариаций индуктона.

Основная идея доказательства эквивалентности заключается в следующем:

1. Сильная индукция подразумевает индукцию.
2. Индукция подразумевает сильную индукцию.
3. Правильный порядок $\mathbb{N}$ подразумевает индукцию [Это доказательство изложено в этом ответе, но с гораздо более подробным описанием]
4. Сильная индукция подразумевает правильный порядок $\mathbb{N}$.

Эквивалентность индукции, сильной индукции и правильного упорядочения на $\mathbb{N}$ следует после доказательства четырех импликаций, изложенных выше (документ, ссылка на который содержит подробности доказательства(й)).

Ответ, который я дал, относится к (3) выше, но вы можете исследовать остальные три, чтобы показать эквивалентность, если хотите.

Методы доказательства: Доказательство с помощью математической индукции

Прошло некоторое время с тех пор, как я в последний раз публиковал что-то о методах доказательства, но давайте еще раз покопаемся и рассмотрим четвертый метод. Первые три были прямым доказательством, доказательством от противного и контрапозитивным доказательством. Доказательство по индукции носит несколько иной характер.

В последнее время я читал довольно много сообщений в блогах, и все они кажутся остроумными и умными, поэтому я действительно хотел добавить шутку прямо здесь о индукции. Но я, честно говоря, не смог найти ни одного, который бы показался мне достаточно забавным. Так что, если бы вы могли просто посмеяться или ухмыльнуться в течение нескольких секунд, прежде чем читать дальше, мой день спасен.

Вернуться к индукционной части. Индукция обычно имеет свою силу в утверждениях типа «Для всех целых чисел k, больших b, P(k) истинно». Для некоторых утверждений мы могли бы доказать это некоторыми из уже рассмотренных методов, но для других это означало бы, что мы должны были бы доказать бесконечность случаев.

Аналогия, которую я вижу повсюду и которую я нахожу вполне уместной, состоит в том, чтобы сравнить индукцию с домино (и я не имею в виду пиццу), которые выстраиваются в ряд. Как только вы сбиваете первую, она сбивает все оставшиеся один за другим. Индукция работает примерно так же.

Нам нужно доказать две вещи, и для пояснения я объясню их в обратном порядке

1. Шаг индукции: мы предполагаем, что P(k) истинно, а затем нам нужно показать, что P(k+1) истинно также. Это то же самое, что сказать, что если мы опрокинем произвольную костяшку домино, то следующая тоже упадет.
2. Базовый случай: Нам нужно доказать базовый случай (P(b) — или, другими словами, нам нужно показать, что мы можем опрокинуть первую костяшку костяшки. 

Как только мы показали эти два случая, тогда, если b=1, мы показали P(1), что по шагу индукции подразумевает, что P(2) истинно, что по шагу индукции подразумевает P(3)….. все путь в бесконечность.

Пример доказательства индукции

Давайте начнем с доказательства того, что Гаусс понял в очень раннем детстве.

Предложение: Для всего следующего верно

Я знаю, что это можно доказать как прямое доказательство, но это довольно легко и поэтому хорошо подходит для примера. Вопрос довольно прост для понимания, поэтому я не буду много объяснять идею.

Базовый случай:  В этой ситуации базовым случаем является N = 1, поэтому нам нужно показать, что утверждение верно для этого

Сумма n от 1 до 1 равна…. 1, так что левая сторона довольно проста. Правую часть легко вычислить, используя базовую арифметику, которую изучают в 1-4 классах, поэтому мы можем сократить утверждение до

1=1

Что верно.
Шаг индукции:  Мы предполагаем, что утверждение верно для N = k так, что оно верно для

, и нам нужно показать, что утверждение также верно для

Проведем эту часть как прямое доказательство.

На первом этапе из суммирования просто выбирается k+1. вторая часть последнего утверждения по предположению равна, поэтому мы имеем

, что доказывает утверждение, что

Таким образом, мы доказали, что оно верно для базового случая n = 1 и что оно верно для всех n по индукции.