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

  • 6 мин чтения
  • Послушать — 4 мин
  • 13 карточек

Алгебра, 9 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин

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

Принцип математической индукции. Если утверждение A(n) верно при n = 1 и из того, что оно верно при каком-то n, следует, что оно верно при n + 1, то оно верно при всех натуральных n.

Метод доказательства

  1. База индукции: проверить утверждение при n = 1.
  1. Предположение индукции: допустить, что оно верно при произвольном натуральном n.
  1. Шаг индукции: опираясь на предположение, доказать его при n + 1.

Пример 1. 2 + 4 + … + 2n = n(n + 1). База: 2 = 1 · 2. Пусть S_n = n(n + 1). Тогда S₍n + 1) = S_n + 2(n + 1) = n(n + 1) + 2(n + 1) = (n + 1)(n + 2) — это и есть формула при n + 1.

Пример 2 (неравенство). 3ⁿ ≥ 1 + 2n при всех натуральных n. База: 3 ≥ 3. Шаг: 3⁽n + 1) = 3 · 3ⁿ ≥ 3(1 + 2n) = 3 + 6n > 1 + 2(n + 1).

Индукция не с единицы. Если утверждение верно лишь начиная с некоторого n₀, базу проверяют при n = n₀, а шаг доказывают для n ≥ n₀. Например, 2ⁿ > n² верно при n ≥ 5: 32 > 25; если 2ⁿ > n² и n ≥ 5, то 2⁽n + 1) > 2n² ≥ (n + 1)², так как n² ≥ 2n + 1 при n ≥ 3.

Главное в шаге — выразить утверждение для n + 1 через утверждение для n (например, S₍n + 1) = S_n + последнее слагаемое) и воспользоваться предположением. База без шага (и шаг без базы) ничего не доказывает.

Зачем это

1 / 13

Для всех n

Многие утверждения говорят о всех натуральных n: «1 + 3 + 5 + … + (2n - 1) = n²».

Проверить все n по очереди нельзя — их бесконечно много.

Как в игре «испорченный телефон»: если первый получил слово и каждый передаёт его следующему, слово дойдёт до любого игрока.

Правило

2 / 13

Принцип индукции

Если утверждение A(n):

  • верно при n = 1,
  • и из того, что оно верно при каком-то n, следует, что оно верно при n + 1,

то A(n) верно при всех натуральных n.

Правило

3 / 13

Три шага метода

  1. База индукции: проверить утверждение при n = 1.
  2. Предположение индукции: допустить, что оно верно при произвольном натуральном n.
  3. Шаг индукции: опираясь на предположение, доказать его при n + 1.

Проверь себя

4 / 13

Хватит ли проверок?

Утверждение проверили при n = 1, 2, 3, …, 100 — везде верно.

Доказано ли оно для всех натуральных n?

нетда
Ответ и объяснение

Проверки дают лишь базу. Нужен ещё шаг: из верности при n вывести верность при n + 1.

Разбор

5 / 13

Сумма нечётных

Докажи для всех натуральных n:

1 + 3 + … + (2n - 1) = n²

  1. База

    n = 1: 1 = 1² — верно.

  2. Предположение

    Пусть S_n = n². Следующее слагаемое: 2(n + 1) - 1 = 2n + 1.

  3. Ответ

    S₍n + 1) = S_n + (2n + 1) = n² + 2n + 1 = (n + 1)².

    Это формула при n + 1 — равенство верно при всех n.

Правило

6 / 13

Главное в шаге

Утверждение для n + 1 выражают через утверждение для n и пользуются предположением.

Для сумм: S₍n + 1) = S_n + слагаемое номер n + 1.

Для степеней: 3⁽n + 1) = 3 · 3ⁿ.

Проверь себя

7 / 13

Что добавить?

S_n = 1 + 4 + 7 + … + (3n - 2)

S₍n + 1) = S_n +

3n + 13n - 23n + 3
Ответ и объяснение

Слагаемое номер n + 1: 3(n + 1) - 2 = 3n + 1.

Разбор

8 / 13

Неравенство

Докажи для всех натуральных n:

2ⁿ ≥ n + 1

  1. База

    n = 1: 2 ≥ 2 — верно.

  2. Шаг

    Пусть 2ⁿ ≥ n + 1. Тогда 2⁽n + 1) = 2 · 2ⁿ ≥ 2(n + 1) = 2n + 2.

  3. Ответ

    2n + 2 ≥ n + 2 = (n + 1) + 1 — неравенство верно при всех n.

Правило

9 / 13

Индукция не с единицы

Если утверждение верно лишь начиная с некоторого n₀:

  • базу проверяют при n = n₀;
  • шаг доказывают для n ≥ n₀.

Пример: 2ⁿ > 2n + 1 неверно при n = 1 и n = 2, но верно при n ≥ 3.

Разбор

10 / 13

База с трёх

Докажи при n ≥ 3:

2ⁿ > 2n + 1

  1. База

    n = 3: 8 > 7 — верно.

  2. Шаг

    Пусть 2ⁿ > 2n + 1, n ≥ 3. Тогда 2⁽n + 1) = 2 · 2ⁿ > 4n + 2.

  3. Ответ

    4n + 2 > 2n + 3 = 2(n + 1) + 1 — неравенство верно при всех n ≥ 3.

Частая ошибка

11 / 13

База без шага

«n² + n + 41 — простое при всех n: проверено при n = 1, 2, …, 39» — неверно!

Проверка: n = 40: 40² + 40 + 41 = 1681 = 41² — составное.

Сколько бы чисел ни проверить, без шага это не доказательство.

Проверь себя

12 / 13

Шаг без базы

A(n): «число 2n + 1 чётное». Шаг верен: 2(n + 1) + 1 = (2n + 1) + 2 — если 2n + 1 чётно, то и это чётно.

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

нет базышаг неверентак доказывать нельзя
Ответ и объяснение

При n = 1: 2 · 1 + 1 = 3 — нечётное. Шаг без базы ничего не доказывает.

Главное

13 / 13

Главное

  • База: проверить A(1) (или A(n₀)).
  • Предположение: A(n) верно при произвольном n.
  • Шаг: доказать A(n + 1), выразив его через A(n): S₍n + 1) = S_n + слагаемое.
  • База без шага и шаг без базы ничего не доказывают.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест