Принцип математической индукции позволяет доказать утверждения \(A_1,A_2,\ldots\) для всех натуральных номеров. Сначала доказывают \(A_1\). Затем для произвольного \(n\in\mathbb N\) показывают: если верно \(A_n\), то верно \(A_{n+1}\). Тогда истинны все
При полной индукции в шаге к \(A_{n+1}\) разрешается использовать истинность всех предыдущих \(A_k\) при \(k\le n\). Полная индукция равносильна
Что важно запомнить
- Сначала доказывается база \(A_1\).
- Индукционный переход \(A_n\Rightarrow A_{n+1}\) доказывается для произвольного \(n\).
- В переходе разрешено пользоваться \(A_n\), но нельзя заранее предполагать \(A_{n+1}\).
- Полная индукция позволяет использовать все утверждения \(A_1,\ldots,A_n\).
- Обычная и полная индукция равносильны аксиоме индукции.
Пусть даны утверждения \(A_1,A_2,\ldots,A_n,\ldots\). Принцип математической индукции говорит: если \(A_1\) истинно и для каждого \(n\in\mathbb N\) из истинности \(A_n\) следует истинность \(A_{n+1}\), то истинны все утверждения
Почему метод работает
Рассмотрим множество \(M\) всех номеров \(n\), для которых \(A_n\) истинно. Доказанная база означает \(1\in M\). Индукционный переход означает, что вместе с \(n\) множество \(M\) содержит \(n+1\). По аксиоме индукции \(M=\mathbb N\). Значит, утверждение доказано для каждого натурального номера. Обратное рассуждение показывает, что принцип математической индукции и аксиома индукции
Полная индукция
В полной математической индукции для доказательства \(A_{n+1}\) можно предполагать истинность всех \(A_k\) с \(k\le n\). Чтобы свести её к обычной индукции, вводят \(B_n\): «все \(A_k\) при \(k\le n\) истинны». Тогда переход \(B_n\Rightarrow B_{n+1}\) имеет обычную индукционную форму. Поэтому полная индукция равносильна
Полная индукция особенно удобна, когда новый объект строится из нескольких меньших. Типичный пример — доказательство существования разложения натурального числа больше 1 на простые
Пример простыми словами
Обычную индукцию удобно увидеть на формуле
\[1+2+\cdots+n=\frac{n(n+1)}{2}.\]
Для \(n=1\) она верна. Если формула верна для \(n\), то после прибавления \(n+1\) получаем
\[\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2},\]
то есть формулу для следующего номера.
Для полной индукции типичен пример разложения на простые множители. База начинается с \(n=2\). Предположим, что все числа от 2 до \(n\) уже раскладываются. Если \(n+1\) составное, то \(n+1=n_1n_2\), где \(1\lt n_1,n_2\le n\). К обоим множителям применимо предположение полной индукции, поэтому и \(n+1\) раскладывается на простые
Частые ошибки
- Проверить несколько первых значений и принять закономерность за доказательство.
- Доказывать переход только для конкретного \(n\) вместо произвольного.
- Использовать в индукционном переходе утверждение \(A_{n+1}\), которое ещё требуется доказать.
