C10 Математическая индукция

Идея метода: математическая индукция — это способ доказать, что некоторое утверждение $P(n)$ верно для всех натуральных чисел $n \geq n_0$, опираясь лишь на два факта: что оно верно в самом начале, и что истинность для $n$ влечёт истинность для $n+1$.

Представь лестницу с бесконечным числом ступеней. Если ты стоишь на первой ступени (база) и знаешь, что с любой ступени можно перешагнуть на следующую (шаг), то ты можешь добраться до любой ступени. Именно эта аналогия объясняет, почему индукция работает: она «разворачивается» в бесконечную цепочку шагов $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \ldots$

Математическая индукция — главный метод доказательства формул для сумм, неравенств, делимости и комбинаторных утверждений, зависящих от натурального параметра $n$. Она незаменима там, где прямое вычисление невозможно (бесконечно много случаев), а структура задачи позволяет передавать истинность «по эстафете».

Существуют три основных разновидности:
- Обычная (полная) индукция: шаг от $P(n)$ к $P(n+1)$;
- Сильная (полная) индукция: шаг от $P(1), P(2), \ldots, P(n)$ к $P(n+1)$ — нужна, когда для шага используется не только предыдущий, но и более ранние случаи;
- Индукция по двум переменным (или нисходящая индукция): применяется для двухпараметрических утверждений или для доказательства через уменьшение.

• Принцип математической индукции (полная). Если $P(n_0)$ верно, и для каждого $n \geq n_0$ из $P(n)$ следует $P(n+1)$, то $P(n)$ верно для всех $n \geq n_0$. Когда использовать: доказываете формулу суммы, произведения, неравенство с натуральным $n$.

• Принцип сильной индукции. Если $P(n_0)$ верно, и для каждого $n > n_0$ из истинности $P(k)$ для всех $k < n$ следует $P(n)$, то $P(n)$ верно для всех $n \geq n_0$. Когда использовать: разложение на слагаемые/множители, задачи, где шаг «перескакивает» более чем на единицу (например, $P(n)$ через $P(n-2)$ и $P(n-3)$).

• Индукция по двум переменным. Если $P(m, n)$ верно при $m = 0$ (или $n = 0$) для всех $n$ (или $m$), и из $P(m, n)$ следует $P(m+1, n)$ и $P(m, n+1)$, то $P(m, n)$ верно для всех $m, n \geq 0$. Когда использовать: задачи на плиточные замощения, пути на сетке, комбинаторные тождества вроде $\binom{m+n}{m}$.

• Нисходящая (обратная) индукция. Доказываем: $P(n)$ верно для бесконечно многих $n$ (например, для всех степеней двойки), и из $P(n)$ следует $P(n-1)$. Когда использовать: неравенства типа AM-GM, где прямой шаг $n \to n+1$ труден, а шаг $n \to n-1$ прост.

• Формула суммы арифметической прогрессии $\sum_{k=1}^n k = \dfrac{n(n+1)}{2}$ — классический пример для полной индукции. Условие: $n \in \mathbb{N}$.

• Проверить базу явно. Подставить $n = n_0$ и убедиться, что равенство/неравенство выполнено. Не пропускать — ошибка в базе обнуляет доказательство.

• Сформулировать предположение индукции (ПИ) чётко. Написать «Предположим, что для некоторого $n = k$ верно: $P(k)$». Это отдельная строка в решении.

• В шаге использовать ПИ явно. При переходе от $P(k)$ к $P(k+1)$ выделить то место, где вы подставляете предположение — фраза «по предположению индукции».

• При сильной индукции — в базе доказать несколько начальных случаев (столько, сколько нужно для первого шага).

• Разбить шаг на случаи. Если $P(k+1)$ зависит от чётности $k$, делимости и т.п. — рассмотреть случаи отдельно.

• Для неравенств: после применения ПИ оценить «хвост» — разность между левой и правой частью при переходе $n \to n+1$ должна быть $\geq 0$.

• Выбор переменной индукции. Не всегда очевидно, по чему индуцировать: по $n$, по числу элементов, по периметру, по сумме. Если один выбор не работает — попробуй другой.

Поверхностные признаки (что буквально написано):
- «Докажите для всех натуральных $n$», «Докажите для всех $n \geq 1$»
- «Докажите, что $1 + 2 + \ldots + n = \ldots$» или аналогичная сумма
- «Докажите, что $n! > 2^n$ при $n \geq \ldots$»
- В условии есть явный натуральный параметр $n$, и утверждение проверяется экспериментально при малых $n$

Структурные признаки (форма выражения, объекты):
- Утверждение о всех натуральных числах (не конечном наборе)
- Выражение рекуррентно: $a_{n+1} = f(a_n)$ или сумма с $n$ слагаемыми
- Задача про разбиения, раскраски на $n$ шагов, пути длины $n$ - Делимость: «$6 \mid n^3 - n$ для любого $n$»

Цель задачи (что от тебя хотят):
- Доказать тождество или неравенство для произвольного $n$ - Доказать существование разложения (например, любое $n \geq 2$ раскладывается в простые)
- Доказать свойство рекурсивно определённой последовательности

Задача 1. Доказать, что $\displaystyle\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$ для всех $n \in \mathbb{N}$.

Источник: классика, тренировочная

Как думать (рассуждение ученика):
1. Что я вижу? Сумма с верхним пределом $n$ и утверждение «для всех $n \in \mathbb{N}$». Триггер сработал: нужна индукция.
2. Какой метод? Обычная полная индукция — шаг от $n=k$ к $n=k+1$.
3. Первый ход: Проверить базу $n=1$: $1^2 = 1$, а $\frac{1 \cdot 2 \cdot 3}{6} = 1$. ✓
4. Ключевая идея: В шаге индукции пишем сумму до $k+1$ как «сумма до $k$» плюс $(k+1)^2$. По ПИ заменяем «сумму до $k$» на известную формулу и упрощаем.

Решение:$

*$База:* При $n=1$: $\sum_{k=1}^1 k^2 = 1 = \frac{1 \cdot 2 \cdot 3}{6}$. Верно.

*Предположение индукции (ПИ$):*$ Предположим, что для некоторого $n = m \geq 1$ верно$$\sum_{k=1}^m k^2 = \frac{m(m+1)(2m+1)}{6}.$$

Шаг: Докажем для $n = m+1$:$$\sum_{k=1}^{m+1} k^2 = \underbrace{\sum_{k=1}^m k^2}_{\text{по ПИ}} + (m+1)^2 = \frac{m(m+1)(2m+1)}{6} + (m+1)^2.$$ Вынесем $(m+1)$:$$= (m+1)\left(\frac{m(2m+1)}{6} + (m+1)\right) = (m+1) \cdot \frac{m(2m+1) + 6(m+1)}{6} = (m+1) \cdot \frac{2m^2+7m+6}{6}.$$ Факторизуем числитель: $2m^2+7m+6 = (m+2)(2m+3) = (m+2)(2(m+1)+1)$. Следовательно,$$\sum_{k=1}^{m+1} k^2 = \frac{(m+1)(m+2)(2(m+1)+1)}{6},$$ что совпадает с формулой при $n = m+1$. Шаг доказан.

По принципу математической индукции формула верна для всех $n \in \mathbb{N}$.

Ответ: формула доказана.

Что в этой задаче было главным: умение переписать сумму до $(m+1)$ через сумму до $m$ и явно сослаться на ПИ. Алгебрическое упрощение — не «магия», а нахождение нужной факторизации.

Задача 2. Докажите, что каждое натуральное число $n \geq 2$ является простым или разлагается в произведение простых чисел.

Источник: классика теории чисел, тренировочная

Как думать (рассуждение ученика):
1. Что я вижу? Утверждение для всех $n \geq 2$. Параметр — натуральное число. Индукция.
2. Какой тип? Обычная индукция не подходит: если $n$ составное, то $n = a \cdot b$ с $a, b < n$, и я хочу использовать утверждение для $a$ и $b$, а не для $n-1$. Это сильная индукция.
3. Первый ход: База $n=2$: число $2$ простое. ✓
4. Ключевая идея: Если $n$ простое — готово. Если $n = a \cdot b$ с $2 \leq a, b < n$, то по сильному ПИ $a$ и $b$ уже раскладываются в произведение простых. Перемножив, получим разложение $n$.

Решение:$

*$База:* $n=2$ — простое число. Утверждение верно.

Сильное предположение индукции: Предположим, что для всех натуральных $2 \leq k < n$ число $k$ является простым или разлагается в произведение простых.

Шаг: Рассмотрим число $n \geq 3$.
- Если $n$ простое, утверждение выполнено.
- Если $n$ составное, то $n = a \cdot b$, где $2 \leq a \leq b < n$. По сильному ПИ, $a = p_1 p_2 \cdots p_r$ и $b = q_1 q_2 \cdots q_s$ для некоторых простых $p_i, q_j$. Тогда $n = p_1 \cdots p_r q_1 \cdots q_s$ — разложение $n$ в произведение простых.

По принципу сильной индукции утверждение верно для всех $n \geq 2$.

Ответ: доказано.

Что в этой задаче было главным: выбор сильной индукции. При обычной индукции шаг $n \to n+1$ не работает, потому что делители $n$ могут быть далеко от $n-1$.

Задача 3. (Нисходящая индукция) Докажите неравенство AM-GM для $n = 2^k$: $\dfrac{a_1 + a_2 + \ldots + a_n}{n} \geq \sqrt[n]{a_1 a_2 \cdots a_n}$ для неотрицательных $a_i$.

Источник: классика, нисходящая индукция по Коши, тренировочная

Как думать (рассуждение ученика):
1. Что я вижу? Неравенство для $n$ чисел, причём хотим $n$ — любое натуральное. Прямой шаг $n \to n+1$ неудобен, зато шаг $n \to 2n$ удвоением — красив.
2. Стратегия Коши: докажем для всех $n = 2^k$ (восходящий шаг удвоения), затем докажем «спуск» $P(n) \Rightarrow P(n-1)$. Вместе это даст все $n$.
3. Ключевая идея восходящего шага: AM-GM для $2n$ чисел сводится к AM-GM для $n$ чисел, применённому дважды — к первой половине и второй.

Решение (восходящий шаг $n \to 2n$):

Пусть $P(n)$ верно. Тогда для $2n$ чисел $a_1, \ldots, a_n, b_1, \ldots, b_n$:$$\frac{a_1+\ldots+a_n+b_1+\ldots+b_n}{2n} = \frac{\bar{a}+\bar{b}}{2} \geq \sqrt{\bar{a}\bar{b}} \geq \sqrt{\sqrt[n]{A}\cdot\sqrt[n]{B}} = \sqrt[2n]{AB},$$ где $\bar{a} = \frac{\sum a_i}{n} \geq \sqrt[n]{A}$ и $\bar{b} \geq \sqrt[n]{B}$ по $P(n)$, а $A = a_1\cdots a_n$, $B = b_1\cdots b_n$.

Нисходящий шаг $P(n) \Rightarrow P(n-1)$: Дано $n-1$ чисел $a_1,\ldots,a_{n-1}$. Положим $a_n = \frac{a_1+\ldots+a_{n-1}}{n-1}$. По $P(n)$:$$\frac{a_1+\ldots+a_{n-1}+a_n}{n} \geq \sqrt[n]{a_1\cdots a_{n-1}\cdot a_n}.$$ Левая часть равна $\frac{(n-1)a_n+a_n}{n} = a_n$. Следовательно, $a_n^n \geq a_1\cdots a_{n-1}\cdot a_n$, откуда $a_n^{n-1} \geq a_1\cdots a_{n-1}$, то есть $\frac{a_1+\ldots+a_{n-1}}{n-1} \geq \sqrt[n-1]{a_1\cdots a_{n-1}}$.

Что в этой задаче было главным: нисходящая индукция позволяет «перепрыгнуть» трудный прямой шаг через доказательство для степеней двойки плюс спуск. Ключевой трюк — добавить вспомогательный элемент, равный среднему.

• Ошибка: Забыть проверить базу. → Почему неверно: без базы цепочка не начинается; классический контрпример — «все лошади одного цвета», где ошибка именно в базе при $n=2$. → Как избежать: всегда начинать решение с явной проверки $P(n_0)$.

• Ошибка: В шаге использовать то, что доказываем, а не то, что предполагаем. → Почему неверно: это порочный круг. → Как избежать: чётко выписать «Предположим для $n = k$» и «Докажем для $n = k+1$» — две разные строки.

• Ошибка: При сильной индукции доказать базу только для $n = n_0$, когда нужны несколько начальных случаев. → Почему неверно: если шаг использует $P(n-2)$, база должна включать $n_0$ и $n_0+1$. → Как избежать: определить, сколько «предыдущих» случаев используется в шаге, и проверить столько же баз.

• Ошибка: Написать «и так продолжаем» вместо формального шага индукции. → Почему неверно: это не доказательство, а описание процесса. → Как избежать: всегда формулировать ПИ и явно использовать его в шаге.

• Ошибка: Применять обычную индукцию там, где нужна сильная. → Почему неверно: шаг $P(k) \Rightarrow P(k+1)$ может не работать, если $P(k+1)$ зависит от $P(k-1)$ или более ранних значений. → Как избежать: спросить себя: «Достаточно ли знания только $P(k)$ для доказательства $P(k+1)$?»

• Ошибка: Считать, что индукция доказывает только «равенства». → Почему неверно: индукция доказывает любые утверждения о натуральных числах: неравенства, делимость, существование, комбинаторные свойства. → Как избежать: применять индукцию шире, особенно в задачах ВсОШ на делимость.