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