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