Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Метод математической индукции

На главную Математический раздел Криптография и т.д. Новости

Сначала простые примеры

Перед тем, как описать метод математической индукции в "умных" словах, приведём примеры, которые помогут уловить суть. Пример 1. Есть вот какая формула:

Эту формулу знали ещё древние. Она верна для всех натуральных n. Можно немного поэкспериментировать. n = 1: и слева, и справа будет 1. n = 2: слева 1 + 3, справа 2*2. n=3: слева 1 + 3 + 5 = 9, справа 3 * 3 = 9. Ну и так далее. Разумеется, несколько таких примеров могут помочь вывести формулу, но ещё не доказывают её. А вдруг при n = 1 234 567 890 это будет неверно?) Мы докажем, что всё верно.

Итак, при n = 1 формула верна. Докажем вот что: если при n формула верна, то при подстановке n+1 вместо n она тоже будет верна:

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

Толкаем крайнюю костяшку в сторону соседней (см. картинку). Она, падая, заваливает соседку, та заваливает следующую кость и так далее. В конце концов даже отдалённые кости будут сменены и сами же будут сметать следующих за ними. Этакая цепная реакция получается)

Пример 2. Теперь ещё примерчик - формула для суммы первых n натуральных чисел:

При n = 1 слева 1, справа 1 * (1 + 1) / 2 = 1. Допустим, для n формула верна. Верна ли она тогда для n+1?

Ничё себе) Она действительно верна для n+1.

Определение метода математической индукции

Ну а теперь собственно определение метода математической индукции. Пусть требуется доказать, что утверждение верно для всех натуральных n, не меньших k. Метод математической индукции - доказательство по следующему алгоритму. 1. Показываем, что утверждение верно для n=k. 2. Доказываем, что из истинности утверждения для любого натурального n, не меньшего k, следует истинность утверждения для n+1. 3. Жёстко посылаем того, кто и после этого нам не верит.

Этап 1 доказательства методом математической индукции - база индукции, этап 2 - индукционный переход.

Реальное применение метода математической индукции

Выше были приведены примеры, когда метод математической индукции позволил доказать пару несложных формул. Но возникает важный вопрос: откуда, собственно, эти формулы взялись? Ведь мы просто доказали уже существующие формулы, доказательство - не вывод, оно куда проще.

Чтобы получить такого рода формулы, как выше, обычно делается следующее: рассматривается несколько более-менее простых частных случаев, и ищется закономерность.

Допустим, мы хотим получить формулу для суммы углов выпуклого n-угольника. Самый простой случай - треугольник - 180 градусов, n = 3.

Далее рассматриваем четырёхугольник и пятиугольник. При n = 4 сумма углов - удвоенная сумма углов треугольника, при n = 5 - утроенная сумма углов треугольника. Напрашивается предположение, что сумма углов шестиугольника - учетверённая сумма углов треугольника и т.д. Словом, возникает предположение, что S(n) = 180(n-2).

А вот теперь ведётся доказательство методом математической индукции, поскольку правильность утверждения на нескольких примерах не означает, что формула всегда сработает. Издевательский пример для подтверждения. Некой совсем молоденькой девушке попался весьма противный субъект, с которым она некоторое время встречалась, но который разочаровал своими поступками. Потом попались ещё несколько в этом роде. Согласитесь, у неё вполне может сложиться противный вывод типа "все мужики - козлы". И тем временем буквально в соседнем квартале в одном из домов в квартире номер Икс может жить ну просто прынц, другое дело, что девушка об этом не будет знать. И даже если они где-то перекутся и начнут коммуникацию, девушка может предвзято отнестись к нему как к потенциальному подлецу.

Вернёмся к формуле. Вооружимся методом математической индукции. Нужно убедиться, что она верна при любых натуральных n от 3 и далее. При n = 3 она верна (база индукции), и мы в этом уже убедились. А теперь делаем индукционный переход. Если от выпуклого n+1 угольника отрезать треугольник, получится выпуклый n-угольник:

Стало быть, S(n+1) = 180 + S(n). Пусть S(n) = 180(n-2), тогда S(n+1) = 180(n-1) = 180(n+1-2). Сработало!

Итак, формулы вида f(n)=g(n), где n - любое натуральное число, не меньшее k, обычно получаются вот как. 1. Формулировка гипотезы по набору частных случаев: берём несколько простых случаев, ищем, какая формула могла бы связать их все воедино. 2. Доказательство (проверка) методом математической индукции: правильность в нескольких случаях ещё не означает, что гипотеза верна во всех предпогалаемых ситуациях (см. пример про девушку).

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X