Лекция 06. Метод математической индукции

Лекция 6. Метод математической индукции.

Новые знания в науке и жизни добываются разными способами, но все они (если не углубляться в детали) делятся на два вида – переход от общего к частному и от частного к общему. Первый – это дедукция, второй – индукция. Дедуктивные рассуждения – это то, что в математике обычно называют логическими рассуждениями, и в математической науке дедукция является единственным законным методом исследования. Правила логических рассуждений были сформулированы два с половиной тысячелетия назад древнегреческим учёным Аристотелем. Он создал полный список простейших правильных рассуждений, силлогизмов – «кирпичиков» логики, одновременно указав типичные рассуждения, очень похожие на правильные, однако неправильные (с такими «псевдологическими» рассуждениями мы часто встречаемся в СМИ).

Индукция (induction – по-латыни наведение) наглядно иллюстрируется известной легендой о том, как Исаак Ньютон сформулировал закон всемирного тяготения после того, как ему на голову упало яблоко. Ещё пример из физики: в таком явлении, как электромагнитная индукция, электрическое поле создает, «наводит» магнитное поле. «Ньютоново яблоко» – типичный пример ситуации, когда один или несколько частных случаев, то есть наблюдения, «наводят» на общее утверждение, общий вывод делается на основании частных случаев. Индуктивный метод является основным для получения общих закономерностей и в естественных, и в гуманитарных науках. Но он имеет весьма существенный недостаток: на основании частных примеров может быть сделан неверный вывод. Гипотезы, возникающие при частных наблюдениях, не всегда являются правильными. Рассмотрим пример, принадлежащий Эйлеру.

Будем вычислять значение трехчлена при некоторых первых значениях n:

n	1	2	3	4	5	6	7	8
	43	47	53	61	71	83	97	113

Заметим, что получаемые в результате вычислений числа являются простыми. И непосредственно можно убедиться, что для каждого n от 1 до 39 значение многочлена является простым числом. Однако при n=40 получаем число 1681=41², которое не является простым. Таким образом, гипотеза, которая здесь могла возникнуть, то есть гипотеза о том, что при каждом n число является простым, оказывается неверной.

Лейбниц в 17 веке доказал, что при всяком целом положительном n число делится на 3, число делится на 5 и т.д. На основании этого он предположил, что при всяком нечётном k и любом натуральном n число делится на k, но скоро сам заметил, что не делится на 9.

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

6.1. Принцип математической индукции.

♦ В основе метода математической индукции лежит принцип математической индукции, заключающийся в следующем:

1) проверяется справедливость этого утверждения для n=1 (базис индукции),

2) предполагается справедливость этого утверждения для n=k, где k – произвольное натуральное число 1 (предположение индукции), и с учётом этого предположения устанавливается справедливость его для n=k+1.

Доказательство. Предположим противное, то есть предположим, что утверждение справедливо не для всякого натурального n. Тогда существует такое натуральное m, что:

1) утверждение для n=m несправедливо,

2) для всякого n, меньшего m, утверждение справедливо (иными словами, m есть первое натуральное число, для которого утверждение несправедливо).

Очевидно, что m>1, т.к. для n=1 утверждение справедливо (условие 1). Следовательно, – натуральное число. Выходит, что для натурального числа утверждение справедливо, а для следующего натурального числа m оно несправедливо. Это противоречит условию 2. ■

Заметим, что в доказательстве использовалась аксиома о том, что в любой совокупности натуральных чисел содержится наименьшее число.

Доказательство, основанное на принципе математической индукции, называется методом полной математической индукции.

 Пример 6.1. Доказать, что при любом натуральном n число делится на 3.

Решение. Воспользуемся методом полной математической индукции.

1) При n=1 , поэтому a₁ делится на 3 и утверждение справедливо при n=1.

2) Предположим, что утверждение справедливо при n=k, , то есть что число делится на 3, и установим, что при n=k+1 число делится на 3.

В самом деле,

.

Т.к. каждое слагаемое делится на 3, то их сумма также делится на 3. ■ 

 Пример 6.2. Доказать, что сумма первых n натуральных нечётных чисел равна квадрату их числа, то есть .

Решение. Воспользуемся методом полной математической индукции.

1) Проверяем справедливость данного утверждения при n=1: 1=1² – это верно.

2) Предположим, что сумма первых k () нечётных чисел равна квадрату числа этих чисел, то есть . Исходя из этого равенства, установим, что сумма первых k+1 нечётных чисел равна , то есть .

Пользуемся нашим предположением и получаем

. ■ 

Метод полной математической индукции применяется для доказательства некоторых неравенств. Докажем неравенство Бернулли.

 Пример 6.3. Доказать, что при и любом натуральном n справедливо неравенство (неравенство Бернулли).

Решение. 1) При n=1 получаем , что верно.

2) Предполагаем, что при n=k имеет место неравенство (*). Используя это предположение, докажем, что . Отметим, что при это неравенство выполняется и поэтому достаточно рассмотреть случай .

Умножим обе части неравенства (*) на число и получим:

, то есть (1+. ■ 

Доказательство методом неполной математической индукции некоторого утверждения, зависящего от n, где проводится аналогичным образом, но в начале устанавливается справедливость для наименьшего значения n.

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

 Пример 6.4. Найти сумму .

Решение. Найдём суммы S₁, S₂, S₃. Имеем , , . Высказываем гипотезу, что при любом натуральном n справедлива формула . Для проверки этой гипотезы воспользуемся методом полной математической индукции.

1) При n=1 гипотеза верна, т.к. .

2) Предположим, что гипотеза верна при n=k, , то есть . Используя эту формулу, установим, что гипотеза верна и при n=k+1, то есть

.

В самом деле,

.

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

 Пример 6.5. В математике доказывается, что сумма двух равномерно непрерывных функций является равномерно непрерывной функцией. Опираясь на это утверждение, нужно доказать, что сумма любого числа равномерно непрерывных функций является равномерно непрерывной функцией. Но поскольку мы ещё не ввели понятие «равномерно непрерывная функция», поставим задачу более абстрактно: пусть известно, что сумма двух функций, обладающих некоторым свойством S, сама обладает свойством S. Докажем, что сумма любого числа функций обладает свойством S.

Решение. Базис индукции здесь содержится в самой формулировке задачи. Сделав предположение индукции, рассмотрим функций f₁, f₂, …, f_n, f_n+1, обладающих свойством S. Тогда . В правой части первое слагаемое обладает свойством S по предположению индукции, второе слагаемое обладает свойством S по условию. Следовательно, их сумма обладает свойством S – для двух слагаемых «работает» базис индукции.

Тем самым утверждение доказано и будем использовать его далее. ■ 

 Пример 6.6. Найти все натуральные n, для которых справедливо неравенство

.

Решение. Рассмотрим n=1, 2, 3, 4, 5, 6. Имеем: 2¹>1², 2²=2², 2³<3², 2⁴=4², 2⁵>5², 2⁶>6². Таким образом, можно высказать гипотезу: неравенство имеет место для каждого . Для доказательства истинности этой гипотезы воспользуемся принципом неполной математической индукции.

1) Как было установлено выше, данная гипотеза истинна при n=5.

2) Предположим, что она истинна для n=k, , то есть справедливо неравенство . Используя это предположение, докажем, что справедливо неравенство .

Т. к. и при имеет место неравенство

при ,

то получаем, что . Итак, истинность гипотезы при n=k+1 следует из предположения, что она верна при n=k, .

Из пп. 1 и 2 на основании принципа неполной математической индукции следует, что неравенство верно при каждом натуральном . ■ 

 Пример 6.7. Доказать, что для любого натурального числа n справедлива формула дифференцирования .

Решение. При n=1 данная формула имеет вид , или 1=1, то есть она верна. Сделав предположение индукции, будем иметь:

,

что и требовалось доказать. ■ 

 Пример 6.8. Доказать, что множество, состоящее из n элементов, имеет  подмножеств.

Решение. Множество, состоящее из одного элемента а, имеет два подмножества. Это верно, поскольку все его подмножества – пустое множество и само это множество, и 2¹=2.

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

Множество В состоит из n элементов, и поэтому, по предположению индукции, у него подмножеств, так что в первом классе подмножеств.

Но во втором классе подмножеств столько же: каждое из них получается ровно из одного подмножества первого класса добавлением элемента d. Следовательно, всего у множества А подмножеств.

Тем самым утверждение доказано. Отметим, что оно справедливо и для множества, состоящего из 0 элементов – пустого множества: оно имеет единственное подмножество – самого себя, и 2⁰=1. ■ 

29