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

Подставим в формулу $p = n^2 - n + 41$ числа $n = 1, 2, 3, \ldots$: $\ 41,\ 43,\ 47,\ 53,\ 61, \ldots$ — все простые. Так продолжается вплоть до $n = 40$.

Но при $n = 41$: $\ p = 41^2 - 41 + 41 = 41^2$ — составное число. Утверждение, проверенное для сорока значений, неверно.

Утверждения «для любого натурального $n$» доказывают особым способом — методом математической индукции.

Если свойство, зависящее от натурального числа $n$, во-первых, верно при $n = 1$ и, во-вторых, из предположения, что оно верно для $n = k$, следует, что оно верно при $n = k + 1$, то считают, что это свойство верно для любого натурального числа $n$.

Первое — база индукции, второе — шаг индукции; предположение «верно для $n = k$» называют предположением индукции. Доказательство, основанное на этом принципе, — доказательство по индукции.

Докажем, что если $a > 0$, то $a^n > 0$ для любого натурального $n$.

База. При $n = 1$ получаем $a > 0$ — верно по условию.

Шаг. Пусть $a^k > 0$. Умножим это неравенство на положительное число $a$: $\ a^{k+1} = a^k \cdot a > 0$.

Оба утверждения выполнены, поэтому по принципу математической индукции $a^n > 0$ для любого натурального $n$.

База. $(1 + b)^1 = 1 + b$ — при $n = 1$ неравенство выполняется (как равенство).

Шаг. Пусть $(1 + b)^k \ge 1 + kb$. Так как $1 + b \ge 0$, неравенство можно умножить на $1 + b$:

$(1 + b)^{k+1} = (1 + b)^k (1 + b) \ge (1 + kb)(1 + b) = 1 + (k + 1)b + kb^2 \ge 1 + (k + 1)b$.

Значит, неравенство верно при любом натуральном $n$. Условие $b \ge -1$ нужно именно на шаге: при умножении на отрицательное число знак неравенства сменился бы.

Не только доказательства, но и определения даются по индукции. Степень с натуральным показателем: $\ a^1 = a$ и $a^{k+1} = a^k \cdot a$ для любого натурального $k$. Например, $a^5 = a^4 \cdot a = a^3 \cdot a \cdot a = \ldots = a \cdot a \cdot a \cdot a \cdot a$.

Докажем $a^m \cdot a^n = a^{m+n}$. Зафиксируем $m$ и будем вести индукцию по $n$.

База. $a^m \cdot a^1 = a^{m+1}$ — это определение степени.

Шаг. Пусть $a^m \cdot a^k = a^{m+k}$. Тогда $a^m \cdot a^{k+1} = a^m \cdot a^k \cdot a = a^{m+k} \cdot a = a^{m+k+1}$. Равенство верно для любых натуральных $m$ и $n$.

• Без базы. «Докажем» неверное неравенство $2^{n+1} < 2^n$: пусть $2^{k+1} < 2^k$; умножив на $2$, получим $2^{k+2} < 2^{k+1}$ — шаг выполнен. Но при $n = 1$ получаем $4 < 2$ — база не выполнена, и утверждение ложно.
• Без шага. Для $p = n^2 - n + 41$ база верна и даже проверены $n = 1, \ldots, 40$, но при $n = 41$ число составное. Конечная проверка шаг не заменяет.
• Индукция с $n_0$. Если утверждение верно лишь начиная с $n_0 > 1$, база — проверка при $n = n_0$, а шаг доказывают для $k \ge n_0$. Тогда утверждение верно для всех $n \ge n_0$.

1. База $n_0 = 3$: $\ 2^3 = 8 > 2 \cdot 3 + 1 = 7$.
2. Предположение. Пусть $2^k > 2k + 1$ при некотором $k \ge 3$. Докажем $2^{k+1} > 2k + 3$.
3. Шаг. $2^{k+1} = 2 \cdot 2^k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k - 1) > 2k + 3$, так как $2k - 1 > 0$.
4. При $n = 1$ и $n = 2$ неравенство неверно ($2 < 3$, $4 < 5$), поэтому база именно $n_0 = 3$.

Чтобы доказать $A(n) = B(n)$ для любого натурального $n$, где $A(n)$ — сумма $n$ слагаемых:

• 1) проверить $A(1) = B(1)$;
• 2) доказать $A(k + 1) - A(k) = B(k + 1) - B(k)$ — слева это просто последнее слагаемое;
• 3) из предположения $A(k) = B(k)$ и равенства 2) следует $A(k + 1) = B(k + 1)$ — шаг индукции выполнен.

1. База. $n = 1$: $\ 1 = \dfrac{1 \cdot 2 \cdot 3}{6}$.
2. Разность сумм. $A(k + 1) - A(k) = (k + 1)^2$.
3. Разность правых частей. $\dfrac{(k + 1)(k + 2)(2k + 3) - k(k + 1)(2k + 1)}{6} = \dfrac{(k + 1)\big(2k^2 + 7k + 6 - 2k^2 - k\big)}{6} = \dfrac{(k + 1)(6k + 6)}{6} = (k + 1)^2$.
4. Разности равны, поэтому из $A(k) = B(k)$ следует $A(k + 1) = B(k + 1)$. Формула верна для всех $n$.

1. База. $5 + 3 = 8$ делится на $4$.
2. Шаг. Пусть $5^k + 3$ делится на $4$. Тогда $5^{k+1} + 3 = 5 \cdot 5^k + 3 = 5(5^k + 3) - 12$.
3. Первое слагаемое делится на $4$ по предположению, $12$ делится на $4$ — значит, и разность делится на $4$.
4. Приём для делимости: выразить выражение при $n = k + 1$ через выражение при $n = k$ плюс заведомо делящееся число.

1. а) $35!$ делится на $9$, значит, и сумма его цифр делится на $9$. Сумма известных цифр $138$, $\ 138 + {*}$ кратно $9$ при ${*} = 6$ (цифра от $0$ до $9$).
2. б) База $n = 1$: $11^3 + 12^3 = 1331 + 1728 = 3059 = 133 \cdot 23$.
3. Шаг. $11^{k+3} + 12^{2k+3} = 11 \cdot 11^{k+2} + 144 \cdot 12^{2k+1} = 11\left(11^{k+2} + 12^{2k+1}\right) + 133 \cdot 12^{2k+1}$. Оба слагаемых делятся на $133$ — да, делится при любом $n$.
4. в) $133 = 7 \cdot 19$. Среди чисел $1, \ldots, 132$ кратны $7$ — $18$ чисел, кратны $19$ — $6$ чисел, общих нет (кратные $133$ больше $132$). Взаимно простых: $132 - 18 - 6 = 108$.

• Индукция: база (верно при $n = 1$ или $n = n_0$) + шаг (из верности при $n = k$ следует верность при $n = k + 1$).
• Без базы или без шага «доказать» можно и ложное утверждение; проверка нескольких $n$ — не доказательство.
• Суммы: проверить $n = 1$ и сравнить приращения левой и правой частей.
• Делимость: выразить выражение при $k + 1$ через выражение при $k$ плюс кратное делителя.
• По индукции и определяют: $a^1 = a$, $a^{k+1} = a^k \cdot a$.