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

  • 5 мин чтения
  • Послушать — 3 мин
  • 11 карточек

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

Индукцией доказывают не только формулы сумм. Схема та же: база, предположение, шаг — меняется лишь то, как из случая n получить случай n + 1.

Делимость. Докажем, что 6ⁿ + 10n - 1 делится на 5. База: 6 + 10 - 1 = 15. Шаг: 6⁽n + 1) + 10(n + 1) - 1 = 6(6ⁿ + 10n - 1) - 50n + 15; первое слагаемое делится на 5 по предположению, а -50n + 15 = 5(3 - 10n) — тоже.

Множества. У множества из n элементов 2ⁿ подмножеств: добавив новый элемент, каждое старое подмножество можно взять с ним или без него — подмножеств становится вдвое больше.

Геометрия. n прямых общего положения делят плоскость на 1 + (n(n + 1))/2 частей: новая, (n + 1)-я прямая пересекает n старых в n точках, делится ими на n + 1 кусков, и каждый кусок разрезает одну часть плоскости надвое.

Размен. Любую сумму от 8 рублей можно набрать монетами по 3 и 5 рублей. База: 8 = 3 + 5. Шаг: если в наборе есть пятирублёвая монета, заменим её двумя трёхрублёвыми (+1 рубль); если нет, то трёхрублёвых не меньше трёх — заменим три из них двумя пятирублёвыми (9 → 10).

Шаг через несколько. Иногда удобнее переходить от n к n + 3 (или n + 2): тогда базу проверяют сразу для нескольких значений подряд. Например, квадрат можно разрезать на 6, 7 и 8 квадратов, а разрезав один из квадратов на четыре, получаем на 3 квадрата больше.

Правило

1 / 11

Та же схема

Индукцией доказывают не только формулы сумм. Схема та же:

база → предположение → шаг.

Меняется лишь то, как из случая n получить случай n + 1: в делимости, в множествах, в геометрии, в задачах на размен.

Разбор

2 / 11

Делимость

Докажи, что при всех натуральных n

5ⁿ + 3 делится на 4

  1. База

    n = 1: 5 + 3 = 8 — делится на 4.

  2. Выделяем

    5⁽n + 1) + 3 = 5(5ⁿ + 3) - 12.

  3. Ответ

    5(5ⁿ + 3) делится на 4 по предположению, 12 — тоже. Значит, 5⁽n + 1) + 3 делится на 4.

Проверь себя

3 / 11

Что прибавить?

Доказываем, что 4ⁿ - 1 делится на 3. В шаге:

4⁽n + 1) - 1 = 4(4ⁿ - 1) + ?

Пропущенное число:

3-3-1
Ответ и объяснение

4(4ⁿ - 1) + 3 = 4⁽n + 1) - 4 + 3 = 4⁽n + 1) - 1; оба слагаемых делятся на 3.

Свойство

4 / 11

Подмножества

У множества из n элементов 2ⁿ подмножеств.

Шаг: добавим новый элемент. Каждое старое подмножество можно взять с ним или без него — подмножеств становится вдвое больше.

{a; b}: ∅, {a}, {b}, {a; b} — 4 = 2².

Наглядно

5 / 11

Прямые на плоскости

Две пересекающиеся прямые делят лист на 4 части; третья прямая пунктиром пересекает их в двух точках, делится ими на 3 куска, и частей становится 7
Две пересекающиеся прямые делят лист на 4 части; третья прямая пунктиром пересекает их в двух точках, делится ими на 3 куска, и частей становится 7

n прямых общего положения делят плоскость на 1 + (n(n + 1))/2 частей. Новая прямая — на n + 1 кусков, каждый режет часть надвое.

Проверь себя

6 / 11

Четыре прямые

Четыре прямые общего положения делят плоскость на части.

Сколько частей?

11816
Ответ и объяснение

1 + (4 · 5)/2 = 11, или 2 + 2 + 3 + 4 = 11.

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

7 / 11

Не общее положение

«Любые 2 прямые делят плоскость на 1 + (2 · 3)/2 = 4 части» — неверно!

Проверка: две параллельные прямые делят плоскость на 3 части.

Формула — только для прямых общего положения: нет параллельных, нет трёх через одну точку.

Разбор

8 / 11

Размен монетами

Докажи, что любую сумму от 4 рублей можно набрать монетами по 2 и 5 рублей.

  1. База

    4 = 2 + 2.

  2. Первый случай

    Есть монета 5 р.: заменим её тремя по 2 р. — сумма выросла на 1.

  3. Ответ

    Пятирублёвых нет: монет по 2 р. не меньше двух — заменим две одной в 5 р.: 4 → 5.

    Любая сумма от 4 р. набирается.

Правило

9 / 11

Шаг через несколько

Иногда удобнее переходить от n к n + 3 (или n + 2). Тогда базу проверяют для нескольких значений подряд.

Квадрат режется на 6, 7 и 8 квадратов (база). Разрезав один квадрат на четыре, получаем на 3 квадрата больше: n → n + 3.

Проверь себя

10 / 11

Сколько баз?

Суммы от 8 р. набираем монетами по 3 и 5 р. Шаг: добавить монету 3 р. (n → n + 3).

Что проверить в базе?

8, 9, 10только 88 и 9
Ответ и объяснение

8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5; шаг +3 от них покрывает все суммы от 8.

Главное

11 / 11

Главное

  • Схема всегда та же: база, предположение, шаг.
  • Делимость: выдели в выражении для n + 1 выражение для n.
  • Подмножества: 2ⁿ; прямые общего положения: 1 + (n(n + 1))/2 частей.
  • Шаг n → n + k — база для k значений подряд.

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

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

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