Метод математической индукции: простыми словами, с задачами

Метод математической индукции — способ доказать утверждение сразу для всех натуральных $n$ : проверяют, что оно верно для первого значения (база), и доказывают, что из верности для $n$ следует верность для $n+1$ (переход). Тогда утверждение верно для 1, значит, для 2, значит, для 3 — и так для любого номера, как в цепочке падающих костяшек домино.

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

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

Пусть есть утверждение $P(n)$ , зависящее от натурального числа $n$ . Например, «сумма первых $n$ нечётных чисел равна $n^2$ ». Проверить его для $n = 1, 2, 3$ легко: $1 = 1^2$ , $1 + 3 = 2^2$ , $1 + 3 + 5 = 3^2$ . Но три проверенных случая — не доказательство: бывают закономерности, которые держатся десятки шагов и ломаются на следующем.

Индукция заменяет бесконечную проверку двумя конечными рассуждениями. В примере с нечётными числами переход выглядит так: если $1 + 3 + \ldots + (2n-1) = n^2$ , то, прибавив следующее нечётное число $2n+1$ , получаем

n^2 + 2n + 1 = (n+1)^2,

то есть утверждение верно и для $n+1$ . Вместе с базой $1 = 1^2$ это доказывает формулу для всех $n$ .

Сформулируйте утверждениеЗапишите точно, что доказывается и для каких n. Иногда удобнее доказывать более сильное утверждение, чем в условии.
Проверьте базуУтверждение должно быть верно для наименьшего нужного значения — иногда это не 1, а 2, 3 или 5.
Сделайте переходПредположите, что утверждение верно для n, и выведите из этого, что оно верно для n + 1. Проверьте, что рассуждение работает для каждого n начиная с базы.
Сделайте выводВерно для базы, а каждый шаг переносит истинность дальше — значит, верно для всех нужных n.

Где индукция ломается: «все лошади одного цвета»

Известный пример ложного доказательства. «Теорема»: в любом табуне из $n$ лошадей все лошади одного цвета.

База: при $n = 1$ в табуне одна лошадь, и она, конечно, одного цвета с собой. Переход: пусть любые $n$ лошадей одного цвета. Возьмём табун из $n+1$ лошади. Уберём первую — останется $n$ лошадей, по предположению они одного цвета. Вернём первую и уберём последнюю — снова $n$ лошадей одного цвета. Лошади «посередине» входят в обе группы, поэтому все $n+1$ лошадей одного цвета.

Ошибка в слове «посередине». При переходе от $n = 1$ к $n = 2$ первая группа — это только вторая лошадь, вторая группа — только первая, и общих лошадей у групп нет. Связать цвета нечем. Переход верен для $n \ge 2$ , но не для $n = 1$ , и цепочка рвётся на первом же звене.

Отсюда два практических правила. Первое: переход должен работать для каждого $n$ начиная с базы, а не только «для больших». Второе: если в переходе вы опираетесь на то, что объектов «хотя бы три» или «есть средний», — проверьте, что при самом маленьком $n$ это так.

Вторая частая ошибка проще: забыть базу. Утверждение « $n^2 + n$ нечётно» обладает корректным переходом — если $n^2 + n$ нечётно, то $(n+1)^2 + (n+1) = (n^2 + n) + 2n + 2$ тоже нечётно. Но базы нет ни при каком $n$ : произведение $n(n+1)$ всегда чётно. Переход без базы ничего не доказывает.

Задача 1: числа Фибоначчи и делимость на 5

1Условие10 классМосковская математическая олимпиада, 1961 год

Дана последовательность чисел $F_1, F_2, \ldots$ ; $F_1 = F_2 = 1$ и $F_{n+2} = F_n + F_{n+1}$ . Доказать, что $F_{5k}$ делится на 5 при $k = 1, 2, \ldots$

Показать решение ↓Скрыть решение ↑

Решение

Индукция по $k$ . Здесь шаг индукции «длинный»: от номера $5k$ к номеру $5k+5$ .

Сначала выразим $F_{n+5}$ через $F_{n+1}$ и $F_n$ , несколько раз применив определение:

\begin{aligned} F_{n+2} &= F_{n+1} + F_n,\\ F_{n+3} &= F_{n+2} + F_{n+1} = 2F_{n+1} + F_n,\\ F_{n+4} &= F_{n+3} + F_{n+2} = 3F_{n+1} + 2F_n,\\ F_{n+5} &= F_{n+4} + F_{n+3} = 5F_{n+1} + 3F_n. \end{aligned}

База: $F_5 = 5$ (последовательность начинается так: $1, 1, 2, 3, 5$ ), делится на 5.

Переход: пусть $F_{5k}$ делится на 5. По формуле выше при $n = 5k$

F_{5k+5} = 5F_{5k+1} + 3F_{5k}.

Первое слагаемое делится на 5 очевидно, второе — по предположению индукции. Значит, и $F_{5(k+1)}$ делится на 5.

ОтветУтверждение доказано: из делимости

F_{5k}

на 5 следует делимость

F_{5k+5}

, а база —

F_5 = 5

Источник задачи: 24-я Московская математическая олимпиада, 1961 год, вариант 1, 10 класс, 1 тур, задача 1 — задача 78251 в базе problems.ru (МЦНМО)

Задача 2: башни из степеней

2УсловиеМосковская математическая олимпиада, 1975 год: пункт а — 7 класс; общий вариант пунктов а и б — 8–10 классы

Какое из двух чисел больше:

а) $2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}$ (100 двоек) или $3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}$ (99 троек);

б) $3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}$ (100 троек) или $4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}$ (99 четвёрок).

Показать решение ↓Скрыть решение ↑

Решение

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

а) Обозначим через $a_n$ башню из $n$ двоек, через $b_n$ — башню из $n-1$ тройки. Тогда $a_{n+1} = 2^{a_n}$ и $b_{n+1} = 3^{b_n}$ . При $n = 2$ первое число больше: $2^2 = 4 > 3$ . Но уже при $n = 3$ картина меняется: $a_3 = 2^{2^2} = 16$ , $b_3 = 3^3 = 27$ . Докажем, что $a_n < b_n$ при всех $n \ge 3$ .

База $n = 3$ : $16 < 27$ . Переход: если $a_n < b_n$ , то

a_{n+1} = 2^{a_n} < 2^{b_n} < 3^{b_n} = b_{n+1}.

Значит, при $n = 100$ больше второе число.

б) Обозначим через $c_n$ башню из $n$ троек, через $d_n$ — башню из $n-1$ четвёрки. Хочется доказать $c_n > d_n$ , но такой переход не проходит: из $c_n > d_n$ следует только $3^{c_n} > 3^{d_n}$ , а сравнивать нужно с $4^{d_n}$ , которое больше $3^{d_n}$ .

Поэтому докажем более сильное неравенство $c_n > 2d_n$ при $n \ge 2$ . База $n = 2$ : $c_2 = 3^3 = 27 > 2 \cdot 4 = 8$ . Переход: если $c_n > 2d_n$ , то

c_{n+1} = 3^{c_n} > 3^{2d_n} = 9^{d_n} > 8^{d_n} = 2^{d_n} \cdot 4^{d_n} \ge 2 \cdot 4^{d_n} = 2d_{n+1}.

Последнее неравенство верно, потому что $d_n \ge 1$ и $2^{d_n} \ge 2$ . Тем более $c_{100} > d_{100}$ .

Ответа) Больше башня из 99 троек; б) больше башня из 100 троек.

Источник задачи: 38-я Московская математическая олимпиада, 1975 год, 2-й тур — пункт а при n = 100 предлагался 7 классу; обе части в общем виде — 8–10 классам. Г. А. Гальперин, А. К. Толпыго, «Московские математические олимпиады», 1986: условия — с. 131–133, решение 38.10 — с. 254. Библиотечные записи: problems.ru, задачи 79299 и 79303. Книга указана в официальном архиве ММО; ссылки на архив и прочитанную копию — в разделе «Источники»

Пункт б — главный приём этой статьи. Если переход не получается, попробуйте доказывать больше: более сильное предположение даёт больше «топлива» для следующего шага. Звучит парадоксально, но доказать $c_n > 2d_n$ оказалось проще, чем $c_n > d_n$ .

Задача 3: обход замка барона Мюнхгаузена

3Условие10 классМосковская математическая олимпиада, 1993 год

Дед барона К. Ф. И. фон Мюнхгаузена построил квадратный замок, разделил его на 9 квадратных залов и в центральном разместил арсенал. Отец барона разделил каждый из восьми оставшихся залов на 9 равных квадратных холлов и во всех центральных холлах устроил зимние сады. Сам барон разделил каждый из 64 свободных холлов на 9 равных квадратных комнат и в каждой из центральных комнат устроил бассейн, а остальные сделал жилыми. Барон хвастается, что ему удалось обойти все жилые комнаты, побывав в каждой по одному разу, и вернуться в исходную (в каждой стене между двумя соседними жилыми комнатами проделана дверь). Могут ли слова барона быть правдой?

Показать решение ↓Скрыть решение ↑

Решение

Каждый из 64 холлов — квадрат $3 \times 3$ из комнат, в центре бассейн, вокруг него 8 жилых комнат. Эти 8 комнат образуют кольцо: обходя его по часовой стрелке, мы побываем в каждой комнате холла и вернёмся в начальную. Все холлы одного размера, поэтому соседние холлы примыкают друг к другу стороной целиком: вдоль общей стены стоят три комнаты одного холла напротив трёх комнат другого.

Холлы образуют связную фигуру: восемь холлов одного зала идут кольцом вокруг зимнего сада, а соседние залы соприкасаются целыми рядами холлов. Поэтому холлы можно занумеровать так, чтобы каждый следующий граничил хотя бы с одним из предыдущих.

Докажем индукцией по $k$ : жилые комнаты первых $k$ холлов можно обойти одним замкнутым маршрутом, причём вдоль каждой стороны холла, за которой ещё нет холла из этих $k$ , маршрут идёт так же, как по кольцу этого холла.

База $k = 1$ : маршрут — кольцо первого холла.

Переход. Пусть новый холл $H$ граничит с уже обойдённым холлом $G$ . Сторона $G$ , обращённая к $H$ , до сих пор свободна, поэтому вдоль неё маршрут идёт по кольцу: в нём есть переход между соседними комнатами $g_1$ и $g_2$ у этой стены. Напротив них в холле $H$ стоят комнаты $h_1$ и $h_2$ , тоже соседние в кольце $H$ . Перестроим маршрут: вместо перехода $g_1 \to g_2$ пойдём из $g_1$ в $h_1$ , обойдём кольцо $H$ длинным путём через все его 8 комнат до $h_2$ и вернёмся в $g_2$ . Получился один замкнутый маршрут по жилым комнатам всех $k+1$ холлов. Изменились только переходы вдоль общей стены $G$ и $H$ , так что вдоль остальных свободных сторон маршрут по-прежнему идёт по кольцам.

При $k = 64$ получаем маршрут по всем $64 \cdot 8 = 512$ жилым комнатам.

ОтветМогут: такой обход существует.

Источник задачи: 56-я Московская математическая олимпиада, 1993 год, 10 класс, задача 2 — задача 107990 в базе problems.ru (МЦНМО), автор задачи — С. Б. Гашков

Обратите внимание на добавку в формулировке: «вдоль свободных сторон маршрут идёт по кольцу». Без неё на шаге $k+1$ нельзя было бы гарантировать, что нужный переход $g_1 \to g_2$ ещё есть в маршруте. Это тот же приём, что в задаче 2: утверждение усилено, чтобы переход сработал.

Задача 4: камни на полоске — родственница «Ханойской башни»

4Условие10 классМосковская математическая олимпиада, 2021 год

Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:

перемещать камень из мешка в первую клетку полоски или обратно;
если в клетке с номером $i$ лежит камень, то можно переложить камень из мешка в клетку с номером $i + 1$ или обратно.

Можно ли, действуя по этим правилам, положить камень в клетку с номером 1000?

Показать решение ↓Скрыть решение ↑

Решение

Ключевое наблюдение: у каждого действия есть обратное. Поэтому любую последовательность действий можно «отмотать назад», выполнив обратные действия в обратном порядке.

Докажем индукцией по $n$ : имея в мешке $n$ камней, можно положить камень в любую клетку с номером от 1 до $2^n - 1$ , пользуясь только клетками не дальше этой. База $n = 1$ : единственный камень кладём в клетку 1.

Переход. Пусть в мешке $n$ чёрных камней и один красный.

Не трогая красный камень, по предположению индукции положим чёрный камень в клетку $2^n - 1$ .
Положим красный камень в клетку $2^n$ — это можно, потому что в соседней клетке слева лежит камень.
Выполним действия из пункта 1 в обратном порядке. Красный камень этому не мешает, ведь те действия касались только клеток до $2^n - 1$ . Теперь все чёрные камни снова в мешке, а на полоске лежит один красный камень в клетке $2^n$ .
Клетки с номерами от $2^n + 1$ до $2^{n+1} - 1$ — это полоска длины $2^n - 1$ , и красный камень слева от неё играет роль «края»: в её первую клетку можно класть камень так же, как в клетку 1. По предположению индукции $n$ чёрными камнями можно положить камень в любую из этих клеток.

Значит, с $n + 1$ камнем доступны все клетки до $2^{n+1} - 1$ . При $n = 10$ это клетки до $2^{10} - 1 = 1023$ , а $1000$ меньше $1023$ .

ОтветДа, можно.

Источник задачи: 84-я Московская математическая олимпиада, 2021 год, 10 класс, задача 3 — официальные решения 10 класса на сайте ММО (МЦНМО), автор задачи — А. Шень

Схема решения напоминает «Ханойскую башню»: сначала освобождают место с помощью меньшего набора объектов, затем выполняют ключевое действие и снова используют меньший набор. В задаче с камнями мы доказали достижимость всех клеток до $2^n - 1$ ; этого достаточно для ответа. Утверждение о том, что дальше пройти нельзя, потребовало бы отдельного доказательства.

Как узнать задачу на индукцию

Явная подсказка — параметр $n$ в условии и вопрос «докажите для всех $n$ ». Но в задачах 3 и 4 никакого $n$ нет: есть 64 холла и 10 камней. Индукция появляется, когда вы замечаете, что большой объект собирается из меньших того же типа, и задаёте себе вопрос: «а если бы холлов было на один меньше, это помогло бы?»

Индукцию можно сочетать с другими методами. В задаче 4 используется обратимость действий; она сама по себе не означает наличия инварианта, а оценки «худшего случая», как в задачах на принцип Дирихле, можно доказывать индукцией по числу объектов. На муниципальном этапе ВсОШ можно встретить задачи на процессы и конструкции, в которых помогает индукция.

Курс по теме

Тематические курсы в записи

Тематические курсы в записи разбирают олимпиадные методы по отдельности — индукцию удобно отработать вместе с инвариантами, принципом Дирихле и комбинаторикой.

Посмотреть курс →

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

С какого класса изучают метод математической индукции?

Жёсткой границы нет: простые задачи на индукцию можно разбирать, как только ученик уверенно работает с буквенными выражениями и умеет записывать рассуждение по шагам. Пункт 2а этой статьи в 1975 году предлагался на Московской олимпиаде семиклассникам. Общий вариант обеих частей задачи 2 предназначался для 8–10 классов.

Обязательно ли начинать базу с единицы?

Нет. База — это наименьшее значение, для которого утверждение должно быть верно. В задаче 2а база $n = 3$, потому что при $n = 2$ нужное неравенство неверно; в задаче 2б база $n = 2$, а в задаче 1 удобнее говорить о номере $5k$ и начинать с $F_5$.

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

Проверка случаев показывает, что утверждение верно для них, и только. Индукция доказывает, что каждый следующий случай следует из предыдущего, поэтому охватывает все $n$ сразу. Несколько проверенных значений полезны, чтобы угадать формулу, но доказательством не являются.

Что делать, если переход не получается?

Сначала проверьте, не опираетесь ли вы на то, что ещё не доказано. Затем попробуйте усилить утверждение, как в задачах 2 и 3, или вести индукцию по другому параметру: не по $n$ из условия, а по числу частей, ходов или объектов.

Источники

problems.ru — задача 78251 — ММО 1961 года, 10 класс, база задач МЦНМО
problems.ru — задача 79299 — ММО 1975 года, 7 класс, база задач МЦНМО
problems.ru — задача 79303 — общий случай задачи о башнях с решением, база задач МЦНМО
problems.ru — задача 107990 — ММО 1993 года, 10 класс, база задач МЦНМО
mmo.mccme.ru — ММО 2021, решения 10 класса — официальный сайт Московской математической олимпиады
Г. А. Гальперин, А. К. Толпыго. «Московские математические олимпиады», 1986 — проверенное первичное издание, указано в официальном архиве ММО. Фибоначчи: условие 24.16 на с. 75, решение на с. 190. Башни: условия на с. 131–133, решение 38.10 на с. 254
«Московские математические олимпиады 1993–2005», 2006 — официальный сборник; ММО 1993, 10 класс, задача 2: условия на с. 20–21, решение на с. 110
«LXXXIV Московская математическая олимпиада. Задачи и решения» — официальная брошюра; ММО 2021, 10 класс, задача 3: условие на с. 9, решение на с. 35–36

Редакция блога «Олмат»Готовит материалы вместе с преподавателями школы. Задачи — из официальных архивов олимпиад.

Метод математической индукции простыми словами

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

Где индукция ломается: «все лошади одного цвета»

Задача 1: числа Фибоначчи и делимость на 5

Задача 2: башни из степеней

Задача 3: обход замка барона Мюнхгаузена

Задача 4: камни на полоске — родственница «Ханойской башни»

Как узнать задачу на индукцию

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

Источники

Принцип Дирихле: олимпиадные задачи с решениями

Задачи на чётность и инвариант с решениями

Математический кружок: как выбрать и чего ждать от занятий

Записаться на бесплатную консультацию

Чем можем помочь?

Метод математической индукции простыми словами

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

Где индукция ломается: «все лошади одного цвета»

Задача 1: числа Фибоначчи и делимость на 5

Задача 2: башни из степеней

Задача 3: обход замка барона Мюнхгаузена

Задача 4: камни на полоске — родственница «Ханойской башни»

Как узнать задачу на индукцию

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

Источники

Читайте также

Принцип Дирихле: олимпиадные задачи с решениями

Задачи на чётность и инвариант с решениями

Математический кружок: как выбрать и чего ждать от занятий

Записаться на бесплатную консультацию