Что проверяют в базе индукции (в первой части доказательства)?

Что утверждение верно при самом первом значении n, обычно n = 1

Что утверждение верно при n = k + 1

Что утверждение верно при n = 1, 2, 3, …, 100

Что из n = k следует n = k + 1

Ученик проверил формулу на компьютере для всех n от 1 до миллиона, и она везде оказалась верной. Доказана ли она для любого натурального n?

Нет, проверка конечного числа случаев не доказывает утверждение для всех n

Да, миллиона проверок достаточно

Да, если проверены и чётные, и нечётные n

Какие части обязательно должны быть в доказательстве методом математической индукции?

Проверка утверждения при первом значении n

Доказательство, что из верности при n = k следует верность при n = k + 1

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

Проверка утверждения при n = 2 и n = 3

Доказываем формулу 1 + 3 + \ldots + (2n - 1) = n². Что нужно получить в шаге индукции?

1 + 3 + … + (2k − 1) + (2k + 1) = (k + 1)²

1 + 3 + … + (2k + 1) = k² + 1

Метод математической индукции — 9 класс, алгебра: объяснение и примеры

Что нужно знать до

Если что-то из этого забылось, начни оттуда — так будет понятнее.

Сумма первых n членов арифметической прогрессии

Коротко о главном

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

\text{база } (n = 1) \ + \ \text{шаг } (k \Rightarrow k + 1) \ \Rightarrow \ \text{верно при любом } n

Подробное объяснение

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

Ряд костяшек домино с номерами 1, 2, 3, …, k, k+1. Первую толкнули — это база; стрелка от k к k+1 — шаг. Вместе они дают падение всех костяшек. — База и шаг вместе: если упала первая и каждая роняет следующую, упадут все.

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

Принцип математической индукции

Утверждение верно при любом натуральном $$n$$ , если выполнены два условия:

База. Утверждение верно при $$n = 1$$ .
Шаг. Если утверждение верно при $$n = k$$ (где $$k$$ — любое натуральное число), то оно верно и при $$n = k + 1$$ .

Предположение «пусть верно при $$n = k$$ » называют предположением индукции. Мы не утверждаем, что оно верно, — мы только показываем, что из него следует верность при $$n = k + 1$$ . Это и есть «каждая упавшая костяшка роняет соседнюю».

Иногда утверждение верно не с единицы, а, скажем, с $$n = 3$$ . Тогда база — проверка при $$n = 3$$ , а шаг доказывают для $k \geqslant 3$ .

Какие утверждения доказывают индукцией

Формулы сумм. В шаге к сумме из предположения прибавляют следующее слагаемое и преобразуют результат к правой части при $$n = k + 1$$ .
Формулы последовательностей, заданных рекуррентно. Предположение подставляют в формулу, по которой из $$a_k$$ получается $a_{k+1}$ .
Делимость. Выражение при $$n = k + 1$$ представляют как сумму двух слагаемых: одно содержит выражение из предположения, другое явно делится на нужное число.
Неравенства. Предположение умножают или складывают с подходящим числом и сравнивают с правой частью при $$n = k + 1$$ .

Как решать задачи

Запишите утверждение при $$n = 1$$ (или с первого нужного номера) и проверьте его вычислением — это база.
Запишите предположение индукции: утверждение при $$n = k$$ .
Запишите, что нужно доказать: то же утверждение, в котором $$n$$ заменено на $$k + 1$$ . Аккуратно подставьте $$k + 1$$ всюду, особенно в последнее слагаемое суммы.
Начните с левой части при $$n = k + 1$$ , выделите в ней кусок из предположения и замените его. Преобразуйте до правой части.
Напишите вывод: «по принципу математической индукции утверждение верно при любом натуральном $$n$$ ».

Разобранные примеры

База

Сумма нечётных чисел

Условие

Докажите, что $1 + 3 + 5 + \ldots + (2n - 1) = n^2$ при любом натуральном $$n$$ .

Решение

База. При $$n = 1$$ : слева $$1$$ , справа $$1^2 = 1$$ . Верно.

Шаг. Пусть $1 + 3 + \ldots + (2k - 1) = k^2$ . Докажем, что $1 + 3 + \ldots + (2k - 1) + (2k + 1) = (k + 1)^2$ . Заменим сумму первых $$k$$ слагаемых на $$k^2$$ :

\[k^2 + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.\]

Вывод. По принципу математической индукции формула верна при любом натуральном $$n$$ .

Ответ: Формула доказана для любого натурального n.

Средний

Делимость на 6

Условие

Докажите, что $$7^n - 1$$ делится на 6 при любом натуральном $$n$$ .

Решение

База. При $$n = 1$$ имеем $$7 - 1 = 6$$ — делится на 6.

Шаг. Пусть $$7^k - 1$$ делится на 6. Запишем выражение при $$n = k + 1$$ , разложив $$7 = 6 + 1$$ :

7^{k+1} - 1 = 7 \cdot 7^k - 1 = 6 \cdot 7^k + (7^k - 1).

Первое слагаемое делится на 6, потому что содержит множитель 6. Второе делится на 6 по предположению. Сумма двух чисел, кратных 6, кратна 6.

Вывод. По принципу математической индукции $$7^n - 1$$ делится на 6 при любом натуральном $$n$$ .

Ответ: Утверждение доказано.

Сложный

Неравенство с другой базой

Условие

Докажите, что $$3^n > n^2 + 1$$ при всех натуральных $n \geqslant 2$ .

Решение

База. При $$n = 2$$ имеем $$3^2 = 9 > 5 = 2^2 + 1$$ . Верно. (При $$n = 1$$ получилось бы $$3 > 2$$ — тоже верно, но для шага нам удобно $k \geqslant 2$ .)

Шаг. Пусть $$3^k > k^2 + 1$$ при некотором $k \geqslant 2$ . Тогда

3^{k+1} = 3 \cdot 3^k > 3(k^2 + 1) = 3k^2 + 3.

Осталось проверить, что $3k^2 + 3 \geqslant (k + 1)^2 + 1 = k^2 + 2k + 2$ . Разность равна $$2k^2 - 2k + 1 = 2k(k - 1) + 1 > 0$$ . Значит, $3^{k+1} > (k + 1)^2 + 1$ .

Вывод. Неравенство верно при всех натуральных $n \geqslant 2$ (а проверка при $$n = 1$$ показывает, что и при $$n = 1$$ ).

Ответ: Неравенство доказано для всех натуральных n.

Типичные ошибки

Проверяют несколько значений n и считают утверждение доказанным

Почему неверно

Любое число проверок конечно, а натуральных чисел бесконечно много. Например, значение $$n^2 + n + 41$$ — простое число при $n = 1, 2, \ldots, 39$ , но при $$n = 40$$ получается $$1681 = 41^2$$ .

Как правильно

Проверка нескольких значений — это только база и самоконтроль. Обязателен шаг: доказательство для произвольного $$k$$ .

Неправильно записывают последнее слагаемое при n = k + 1

Почему неверно

В сумме $1 + 3 + \ldots + (2n - 1)$ при $$n = k + 1$$ последнее слагаемое не $$2k - 1 + 1$$ и не $$2k$$ , а $$2(k + 1) - 1 = 2k + 1$$ . С неверным слагаемым шаг «не сходится», и ученик думает, что формула ошибочна.

Как правильно

Подставляйте $$k + 1$$ вместо $$n$$ в общую формулу слагаемого и раскрывайте скобки. Полезно выписать два последних слагаемых: $\ldots + (2k - 1) + (2k + 1)$ .

Забывают базу

Почему неверно

Шаг без базы может «доказать» ложное. Пусть утверждение: « $$n + 1 = n$$ ». Если $$k + 1 = k$$ , то, прибавив 1, получим $$k + 2 = k + 1$$ — шаг формально проходит. Но при $$n = 1$$ получается $$2 = 1$$ , база неверна, и цепочка не начинается: первую костяшку никто не толкнул.

Как правильно

Всегда начинайте с проверки при первом значении $$n$$ и записывайте её явно.

Проверь себя

Ответь на вопросы — после каждого ответа появится пояснение.

Проверь себя по всему разделу

Задачи для тренировки

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

База Задача 1

Известно, что сумма первых $$n$$ нечётных чисел равна $$n^2$$ , то есть $1 + 3 + 5 + \ldots + (2n - 1) = n^2$ . Найдите по этой формуле сумму $1 + 3 + 5 + \ldots + 39$ .

Подсказка

Число 39 — какое по счёту нечётное число? Решите $$2n - 1 = 39$$ .

Решение

Последнее слагаемое $$2n - 1 = 39$$ , откуда $$n = 20$$ . Сумма равна $$n^2 = 20^2 = 400$$ .

Ответ

400

База Задача 2

Докажите методом математической индукции, что $2 + 4 + 6 + \ldots + 2n = n(n + 1)$ при любом натуральном $$n$$ .

Подсказка

В шаге прибавьте к $$k(k + 1)$$ следующее слагаемое $$2(k + 1)$$ и вынесите $$(k + 1)$$ за скобки.

Решение

База. При $$n = 1$$ : слева $$2$$ , справа $1 \cdot 2 = 2$ . Верно.

Шаг. Пусть $2 + 4 + \ldots + 2k = k(k + 1)$ . Тогда $2 + 4 + \ldots + 2k + 2(k + 1) = k(k + 1) + 2(k + 1) = (k + 1)(k + 2)$ — это формула при $$n = k + 1$$ .

Вывод. По принципу математической индукции формула верна при любом натуральном $$n$$ .

Ответ

Доказано

Средний Задача 3

Докажите, что $1 + 2 + 4 + \ldots + 2^{n-1} = 2^n - 1$ при любом натуральном $$n$$ .

Подсказка

Следующее слагаемое после $2^{k-1}$ — это $$2^k$$ .

Решение

База. При $$n = 1$$ : слева $$2^0 = 1$$ , справа $$2^1 - 1 = 1$$ . Верно.

Шаг. Пусть $1 + 2 + \ldots + 2^{k-1} = 2^k - 1$ . Прибавим $$2^k$$ : получим $2^k - 1 + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1$ — формула при $$n = k + 1$$ .

Вывод. Формула верна при любом натуральном $$n$$ .

Ответ

Доказано

Средний Задача 4

Докажите, что число $$4^n + 2$$ делится на 3 при любом натуральном $$n$$ .

Подсказка

Запишите $4^{k+1} + 2$ как $$4(4^k + 2) - 6$$ .

Решение

База. При $$n = 1$$ имеем $$4 + 2 = 6$$ — делится на 3.

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

Вывод. По принципу математической индукции $$4^n + 2$$ делится на 3 при любом натуральном $$n$$ .

Ответ

Доказано

Сложный Задача 5

Докажите, что $$2^n > 2n + 1$$ при любом натуральном $n \geqslant 3$ .

Подсказка

База здесь — $$n = 3$$ . В шаге умножьте предположение на 2 и сравните $$4k + 2$$ с $$2k + 3$$ .

Решение

База. При $$n = 3$$ имеем $2^3 = 8 > 7 = 2 \cdot 3 + 1$ . Верно.

Шаг. Пусть $$2^k > 2k + 1$$ при некотором $k \geqslant 3$ . Тогда $2^{k+1} = 2 \cdot 2^k > 2(2k + 1) = 4k + 2$ . Так как $$4k + 2 - (2k + 3) = 2k - 1 > 0$$ , получаем $2^{k+1} > 2k + 3 = 2(k + 1) + 1$ .

Вывод. Неравенство верно при всех натуральных $n \geqslant 3$ . (При $$n = 1$$ и $$n = 2$$ оно неверно: $$2 < 3$$ , $$4 < 5$$ , — поэтому база именно $$n = 3$$ .)

Ответ

Доказано для всех n ≥ 3

Сложный Задача 6

Докажите, что $\dfrac{1}{1 \cdot 3} + \dfrac{1}{3 \cdot 5} + \ldots + \dfrac{1}{(2n - 1)(2n + 1)} = \dfrac{n}{2n + 1}$ при любом натуральном $$n$$ .

Подсказка

Следующее слагаемое — $\dfrac{1}{(2k + 1)(2k + 3)}$ . Приведите к общему знаменателю и разложите числитель на множители.

Решение

База. При $$n = 1$$ имеем $\dfrac{1}{1 \cdot 3} = \dfrac{1}{3}$ и $\dfrac{1}{2 + 1} = \dfrac{1}{3}$ . Верно.

Шаг. Пусть сумма $$k$$ слагаемых равна $\dfrac{k}{2k + 1}$ . Тогда сумма $$k + 1$$ слагаемых

\dfrac{k}{2k + 1} + \dfrac{1}{(2k + 1)(2k + 3)} = \dfrac{2k^2 + 3k + 1}{(2k + 1)(2k + 3)} = \dfrac{(k + 1)(2k + 1)}{(2k + 1)(2k + 3)} = \dfrac{k + 1}{2k + 3},

а это формула при $$n = k + 1$$ .

Вывод. Формула верна при любом натуральном $$n$$ .

Ответ

Доказано

Для родителя

Как объяснить за 5 минут. Поставьте в ряд книги или костяшки домино и спросите: что нужно знать, чтобы быть уверенным, что упадут все? Ребёнок придёт к двум условиям: толкнули первую и каждая роняет следующую. Затем покажите это на формуле $1 + 3 + 5 + \ldots + (2n - 1) = n^2$ : база — $$1 = 1^2$$ , шаг — к $$k^2$$ прибавляем следующее нечётное число $$2k + 1$$ и получаем $$(k + 1)^2$$ .

Вопросы для проверки понимания: 1) Почему нельзя доказать формулу, проверив её для первых ста чисел? 2) Что такое предположение индукции и доказываем ли мы его? 3) Что нужно получить в шаге для формулы $2 + 4 + \ldots + 2n = n(n + 1)$ ?

На что обратить внимание. Каждое доказательство должно состоять из трёх частей — база, шаг, вывод — и в шаге должно быть явно видно, где использовано предположение. Самая частая техническая ошибка — неверное слагаемое с номером $$k + 1$$ .

Где в учебниках

Учебник	Параграф	Упражнения
Алгебра. 9 класс (Макарычев, Миндюк, Нешков, Суворова)	§ 31	629, 630, 631, 632, 633, 634, 635, 636