"Алгебра. (в 2 частях)", Петерсон Л.Г., Агаханов Н.Х., Петрович А.Ю., Подлипский О.К., Рогатова М.В., Трушин Б.В.
Принцип математической индукции — способ доказать, что утверждение верно для каждого натурального числа начиная с заданного. Для этого проверяют его при первом допустимом значении, а затем доказывают переход от любого n к n + 1. Представьте ряд падающих костяшек: нужно убедиться, что упала первая, и что каждая следующая падает вслед за предыдущей. Так можно обосновать формулы для сумм, неравенства и делимость, не перебирая бесконечно много чисел.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Принцип математической индукции — способ доказать утверждение для всех натуральных n: проверить его для первого значения и доказать переход от любого значения к следующему. Это не перебор бесконечного числа случаев, а общий механизм доказательства. Он особенно полезен, когда утверждение зависит от натурального числа и его можно связать с соседним значением.
База индукции — проверка утверждения для наименьшего значения n, с которого оно должно быть верным. Например, если доказывают формулу при n ≥ 2, базой будет проверка при n = 2, а не при n = 1. Эта проверка запускает дальнейшую цепочку переходов.
Индукционное предположение — допущение, что утверждение верно для некоторого произвольного n из рассматриваемого множества. Его записывают отдельно, например: «Пусть 1 + 2 + … + n = n(n + 1)/2». Предположение нужно как условие для доказательства следующего значения, а не как готовое доказательство для всех n.
Шаг индукции — доказательство того, что из истинности утверждения для n следует его истинность для n + 1. Для этого выражение при n + 1 преобразуют, используя предположение или известные свойства чисел. Шаг связывает соседние случаи и позволяет продолжить доказательство от базы.
Проверка нескольких первых значений помогает заметить закономерность, но не доказывает утверждение для всех натуральных чисел. Даже если формула верна для первых ста значений, неизвестно, не появится ли исключение на следующем. Индукция отличается от перебора тем, что обосновывает общий переход, применимый к любому следующему числу.
Сначала определяют диапазон, для которого требуется доказательство, и находят его наименьшее n. Затем подставляют это значение в утверждение и проверяют равенство, неравенство или делимость непосредственно. Если база выбрана неверно или вовсе не указана, цепочка доказательства не начинается с нужного места.
В переходе формулируют предположение для произвольного n из диапазона. Например, если доказывается равенство, записывают его так, как будто оно верно при n, и используют эту запись как условие. Нельзя сразу написать, что равенство верно при n + 1: именно это ещё предстоит получить.
Чтобы выполнить переход, записывают доказываемое выражение для n + 1 и преобразуют его до формы, связанной с выражением для n. В сумме часто выделяют последние слагаемые, в степенях пользуются свойствами степеней, а при делимости стараются представить выражение как сумму или произведение известных частей. Так становится понятно, где именно применяется предположение.
База подтверждает утверждение для первого числа, а переход передаёт его истинность следующему. Если база верна, переход даёт верность для следующего значения; применяя тот же довод снова, получают все последующие значения. Поэтому для бесконечного ряда натуральных чисел достаточно одного начального случая и общего доказательства перехода.
| Этап | Что проверяем или доказываем | Что используем | К чему приходим |
|---|---|---|---|
| База индукции | Утверждение при первом допустимом n | Подстановку этого значения и прямую проверку | Утверждение верно в начальном случае |
| Индукционное предположение | Фиксируем произвольное n из нужного диапазона | Предположение, что утверждение верно при n | Получаем условие для перехода |
| Шаг индукции | Утверждение при n + 1 | Предположение для n и преобразования | Истинность передаётся следующему значению |
| Вывод | Все значения от начального и далее | Базу и доказанный переход | Утверждение верно во всём заданном диапазоне |
Пользуйтесь таблицей как планом: сначала установите начальное значение, затем запишите предположение и только после этого доказывайте переход. В выводе обязательно укажите диапазон n, который удалось охватить.
Задача. Докажите по индукции, что 1 + 2 + … + n = n(n + 1)/2 для всех натуральных n. Нужно проверить формулу сначала, а затем связать сумму из n + 1 с суммой из n. В шаге будем использовать предположение о формуле для n.
База: при n = 1 левая часть равна 1, правая — 1·2/2 = 1. Формула верна.
Предположение: пусть 1 + 2 + … + n = n(n + 1)/2. Для следующего значения добавим к левой части новое слагаемое n + 1.
Переход: 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2. Это правая часть формулы при n + 1, поэтому переход доказан.
Ответ: формула верна для всех натуральных n по принципу математической индукции. Выражение для n + 1 получилось именно после применения предположения, а не из отдельной проверки.
Задача. Докажите, что 7^n − 1 делится на 6 для всех натуральных n. Удобно показать, как выражение для следующей степени содержит выражение из предположения. Тогда делимость можно будет получить из делимости слагаемых.
База: при n = 1 имеем 7¹ − 1 = 6, а 6 делится на 6.
Предположение: пусть 7^n − 1 делится на 6. Значит, это выражение можно представить как 6k, где k — целое число.
Переход: 7^(n + 1) − 1 = 7·7^n − 1 = 7(7^n − 1) + 6. Первое слагаемое делится на 6 по предположению, второе также делится на 6, значит, их сумма делится на 6.
Ответ: 7^n − 1 делится на 6 при любом натуральном n. В доказательстве существенно не просто сослаться на предположение, а выделить соответствующую часть выражения.
Задача. Докажите, что 2^n > n + 1 для всех натуральных n ≥ 2. Начинать нужно именно с 2, потому что это первое значение заданного диапазона. Для перехода сравним удвоенную левую часть с требуемой правой частью следующего неравенства.
База: при n = 2 получаем 2² = 4, а 2 + 1 = 3. Неравенство 4 > 3 верно.
Предположение: пусть для некоторого n ≥ 2 выполняется 2^n > n + 1. Умножим обе части на 2; знак строгого неравенства сохраняется, так как 2 положительно.
Переход: 2^(n + 1) = 2·2^n > 2(n + 1). Так как n ≥ 2, то 2(n + 1) ≥ n + 2, следовательно, 2^(n + 1) > n + 2.
Ответ: неравенство верно для всех натуральных n ≥ 2. Проверка базы и доказанный переход охватывают весь указанный диапазон.
Проверять утверждение только для нескольких первых n — значит подменять доказательство наблюдением. Так делают, потому что примеры быстро создают впечатление закономерности, но конечное число случаев не исключает исключения дальше. Проверьте себя: есть ли общий переход, а не только вычисления для отдельных чисел?
Не указывать начальное значение или проверять базу не для того n — значит оставлять часть требуемого диапазона без основания. Ошибка возникает, когда автоматически начинают с единицы, не читая условие. Проверьте, с какого именно значения должно быть верно утверждение, и подставьте его.
Считать утверждение при n + 1 уже истинным — значит принять цель доказательства за готовый факт. Это легко сделать, если записать нужную формулу без обоснования. Проверьте: в начале шага разрешено предполагать только случай n, а случай n + 1 должен быть получен в результате.
Сослаться на предположение, не преобразовав выражение для n + 1, недостаточно. Такая ссылка не показывает, как условие помогает достичь цели. Проверьте, выписаны ли равенства или неравенства, связывающие выражение при n + 1 с предположением для n.
Для индукционных доказательств нужны навыки преобразования алгебраических выражений, а также доказательства равенств, неравенств и делимости. Основа метода — свойства натуральных чисел и переход от n к n + 1, то есть последовательное движение по числовому ряду. Индукция пригодится, когда требуется подтвердить формулу для суммы, свойство степеней или утверждение о делимости для всех натуральных значений.
Почему нельзя просто проверить формулу для первых десяти натуральных чисел?
Первые десять проверок показывают, что формула верна только для этих десяти чисел. Для одиннадцатого и последующих значений может появиться исключение. Индукция доказывает переход, который охватывает все следующие числа.
Обязательно ли начинать индукцию с n = 1?
Нет, начинать нужно с наименьшего значения, для которого требуется доказать утверждение. Например, для условия n ≥ 2 база проверяется при n = 2. После этого доказывают переход от каждого n ≥ 2 к n + 1.
Что именно можно считать известным в индукционном переходе?
Можно предположить, что утверждение верно для произвольного выбранного n из нужного диапазона. Это и есть индукционное предположение. Истинность утверждения для n + 1 считать известной нельзя — её требуется доказать.
Как понять, что индукционный переход доказан?
Нужно показать, что при условии истинности утверждения для n оно обязательно верно и для n + 1. Обычно выражение при n + 1 преобразуют и используют предположение для n. В конце должно быть ясно, почему цель достигнута, а не только приведено похожее выражение.
Можно ли применять математическую индукцию к неравенствам и утверждениям о делимости?
Да. В шаге индукции используют соответственно свойства неравенств или делимости вместе с предположением для n. Метод подходит не только для равенств, но и для самых разных утверждений, зависящих от натурального числа.
1.3.1.* Принцип математической индукции
