🔀 Дискретка

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

Q: Можно ли начать базу не с 1?

Да: базой служит любое подходящее $n_0$, а вывод верен для всех $n \ge n_0$. Например, $2^n > n^2$ верно при $n = 1$ и при всех $n \ge 5$: доказывают базу $n = 5$ и переход, а $n = 2, 3, 4$ — исключения, которые формулой не накрыты.

англ. Mathematical induction

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

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

(P (1) \land \forall k (P (k) \Rightarrow P (k + 1))) \Rightarrow \forall n \geq 1 P (n)

принцип математической индукции: база P(1) и переход P(k) ⇒ P(k+1) гарантируют P(n) для каждого натурального n

Как конечное рассуждение накрывает бесконечное множество? Цепочкой: база даёт $P (1)$ ; переход превращает $P (1)$ в $P (2)$ ; снова переход — $P (3)$ , и так далее. Каждый шаг обеспечен доказанным переходом, старт — базой; разорвать цепь негде. Формально это аксиома натуральных чисел (аксиома Пеано): без неё «индукция» была бы красивой, но необоснованной идеей. Заметьте: переход — это импликация, доказывать $P (k)$ как факт не нужно, нужно лишь показать, что из $P (k)$ вытекает $P (k + 1)$ .

1 + 2 + … + n = n(n+1)/2 — по шагам индукции

Открывай шаги

Сначала попробуйте сделать шаг сами, потом открывайте и сверяйтесь. За полный проход начисляется XP.

Где применяется: формулы сумм и степеней, делимость (например, $n^{3} - n$ делится на 6 — три подряд идущих множителя дают двойку и тройку), неравенства, существование и корректность алгоритмов. Отдельный крупный сюжет — решение рекуррент: индукция проверяет формулу, найденную через характеристическое уравнение, а растущие произведения вроде $n!$ живут в термине факториал.

Частые вопросы

Почему конечное доказательство охватывает бесконечно много случаев?

Потому что оно описывает механизм, а не перечисление. Переход $P (k) \Rightarrow P (k + 1)$ — универсальная инструкция «из верного шага сделать следующий». База запускает цепочку, и она накрывает все $n$ без единого пропуска — перебор тут не нужен.

Можно ли начать базу не с 1?

Да: базой служит любое подходящее $n_{0}$ , а вывод верен для всех $n \geq n_{0}$ . Например, $2^{n} > n^{2}$ верно при $n = 1$ и при всех $n \geq 5$ : доказывают базу $n = 5$ и переход, а $n = 2, 3, 4$ — исключения, которые формулой не накрыты.

Чем индукция отличается от рекурсии?

Направлением мысли. Рекурсия раскручивает задачу сверху вниз до базы, индукция собирает результат снизу вверх: от базы по шагам перехода. Математически это два взгляда на одну конструкцию, и в программах рекурсивные функции корректность доказывают именно индукцией.