1.3.2.* Применение метода математической индукции в разных задачах

Определения и обозначения

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

База индукции — проверка утверждения для первого значения n, входящего в рассматриваемый диапазон. Например, если доказательство требуется для всех n ≥ 1, базой будет случай n = 1. Эта проверка задаёт исходный случай, от которого можно начать переход.

Индукционное предположение — допущение, что утверждение верно для некоторого произвольного натурального k. Оно не означает, что утверждение уже доказано для всех чисел: это временная опора для одного шага рассуждения. Предположение позволяет заменить часть выражения при k + 1 уже известной формулой для k.

Индукционный переход — доказательство того, что из истинности утверждения при n = k следует его истинность при n = k + 1. В нём нужно показать именно эту связь, используя предположение и преобразования. Вместе с базой переход даёт доказательство для всех следующих значений n.

Как это устроено

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

В формулах для сумм сумма при n = k + 1 состоит из суммы первых k членов и ещё одного, последнего члена. Поэтому её записывают как сумму до k плюс член с номером k + 1. Подставив в первую часть формулу из предположения, получают выражение, которое можно преобразовать к формуле для k + 1. Так переход строится не на догадке, а на точном составе суммы.

Для доказательства делимости важно представить выражение при k + 1 так, чтобы в нём появилось выражение при k. Если оно делится на заданное число по предположению, умножение на целое число сохраняет делимость; отдельное слагаемое тоже можно выбрать кратным тому же числу. Тогда всё выражение при k + 1 делится на это число, поскольку сумма кратных ему слагаемых также кратна ему.

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

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

Схема доказательства методом математической индукции

Заполняйте этапы по порядку: сначала зафиксируйте, с какого n начинается утверждение, а затем сформулируйте предположение для произвольного k. В переходе отдельно укажите, где именно использовали предположение. Только после проверки базы и перехода можно записать общий вывод.

Разбор задач

Формула суммы

Докажите, что 1 + 2 + … + n = n(n + 1)/2 для любого натурального n. Здесь левая часть зависит от n, поэтому проверим начальное значение, а затем добавим к сумме при k её новый последний член. Цель перехода — получить правую часть формулы с k + 1 вместо n.

1. База: при n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1. Равенство выполняется.
2. Предположим, что 1 + 2 + … + k = k(k + 1)/2 для произвольного натурального k.
3. При n = k + 1 сумма равна 1 + 2 + … + k + (k + 1). По предположению это k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2.
4. Получили формулу n(n + 1)/2 с n = k + 1, значит переход доказан.

Ответ: равенство верно для любого натурального n по математической индукции.

Делимость

Докажите, что 7ⁿ − 1 делится на 6 для любого натурального n. Удобно при переходе выделить выражение 7ᵏ − 1, потому что его делимость будет известна из предположения. Проверка базы нужна отдельно: из одного перехода исходный случай не следует.

1. База: при n = 1 получаем 7 − 1 = 6, а 6 делится на 6.
2. Предположим, что 7ᵏ − 1 делится на 6, то есть равно 6m для некоторого целого m.
3. Для следующего значения преобразуем: 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6. Первое слагаемое делится на 6 по предположению, второе тоже делится на 6, значит их сумма делится на 6.

Ответ: 7ⁿ − 1 делится на 6 при любом натуральном n.

Неравенство

Докажите, что 2ⁿ ≥ n + 1 для любого натурального n. На следующем шаге степень можно представить как 2 · 2ᵏ, а для второй части использовать предположение. После этого требуется сравнить полученную границу с k + 2.

1. База: при n = 1 имеем 2¹ = 2 и 1 + 1 = 2, поэтому неравенство верно.
2. Предположим, что 2ᵏ ≥ k + 1 для произвольного натурального k. Умножаем обе части на 2: 2ᵏ⁺¹ ≥ 2(k + 1).
3. Так как k ≥ 0, то 2(k + 1) − (k + 2) = k ≥ 0. Значит, 2(k + 1) ≥ k + 2, и потому 2ᵏ⁺¹ ≥ k + 2.

Ответ: 2ⁿ ≥ n + 1 для любого натурального n.

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

Проверять только несколько первых значений n — значит подтвердить утверждение лишь для этих чисел. Так поступают, потому что начальные примеры часто выглядят убедительно, но особое значение может встретиться позже. Проверьте себя: в доказательстве должен быть переход для произвольного k, а не список вычислений.

Переход без произвольного k или без индукционного предположения не связывает соседние случаи. Иногда ученик сразу пишет результат для k + 1, не показывая, откуда он следует. Проверьте, что в рассуждении явно записано предположение при k и показано, где оно используется.

Ошибка в добавлении последнего члена или раскрытии скобок меняет само выражение, которое требуется доказать. Её легко допустить, торопясь перейти к знакомой формуле. Подставьте маленькое значение k и сравните исходную сумму при k + 1 с записанным выражением; затем перепроверьте преобразования.

Если забыть базу или начать её не с того значения, переход может быть верным, но цепочка не запустится. Часто базой автоматически считают n = 1, даже когда утверждение задано начиная с другого числа. Сверьте базу с диапазоном задачи и отдельно подставьте это первое значение в утверждение.

Связь с другими темами

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

Метод применяют к формулам для сумм и степеней, утверждениям о делимости и неравенствам, зависящим от натурального числа. Его используют и в геометрии, когда свойство конфигурации сохраняется при переходе от k объектов к k + 1. В каждом случае меняется вид перехода, но доказательство по-прежнему требует базы и обоснованного шага.

Что запомнить

• Индукционное доказательство состоит из базы и перехода.
• В базе проверяют исходное значение n.
• В предположении утверждение считают верным для произвольного k.
• В переходе доказывают утверждение для k + 1.
• База и переход вместе обеспечивают истинность утверждения для всех последующих натуральных n.
• При переходе важно использовать предположение, а не считать его уже доказанным для всех значений.