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

         Метод доказательства, основанный на аксиоме Пеано 4, используют для доказательства многих математических свойств и различных утверждений. Основой для этого служит следующая теорема.

Теорема. Если утверждение А(n) с натуральной переменной n истинно для n = 1 и из того, что оно истинно для n = k, следует, что оно истинно и для следующего числа n=k, то утверждение А(n) истинно для любого натурального числа n.

Доказательство. Обозначим через М множество тех и только тех натуральных чисел, для которых утверждение А(n) истинно. Тогда из условия теоремы имеем: 1) 1М; 2) k M kM. Отсюда, на основании аксиомы 4, заключаем, что М = N, т.е. утверждение А(n) истинно для любого натурального n.

Метод доказательства, основанный на этой теореме, называется методом математической индукции, а аксиома – аксиомой индукции. Такое доказательство состоит из двух частей:

1) доказывают, что утверждение А(n) истинно для n = 1, т.е. что истинно высказывание А(1);

2) предполагают, что утверждение А(n) истинно для n = k, и, исходя из этого предположения, доказывают, что утверждение A(n) истинно и для n = k + 1, т.е. что истинно высказывание A(k)  A(k + 1).

Если А(1)  А(k)  A(k + 1) – истинное высказывание, то делают вывод о том, что утверждение A(n) истинно для любого натурального      числа n.

         Доказательство методом математической индукции можно начинать не только с подтверждения истинности утверждения для n = 1, но и с любого натурального числа m. В этом случае утверждение А(n) будет доказано для всех натуральных чисел nm.

         Задача. Докажем, что для любого натурального числа истинно равенство 1 + 3 + 5 … + (2n – 1) = n.

         Решение. Равенство 1 + 3 + 5 … + (2n – 1) = n представляет собой формулу, по которой можно находить сумму первых последовательных нечетных натуральных чисел. Например, 1 + 3 + 5 + 7 = 4= 16 (сумма содержит 4 слагаемых), 1 + 3 + 5 + 7 + 9 + 11 = 6= 36 (сумма содержит 6 слагаемых); если эта сумма содержит 20 слагаемых указанного вида, то она равна 20= 400 и т.д. Доказав истинность данного равенства, получим возможность находить по формуле сумму любого числа слагаемых указанного вида.

1) Убедимся в истинности данного равенства для n = 1. При n = 1 левая часть равенства состоит из одного члена, равного 1, правая часть равна 1= 1. Так как 1 = 1, то для n = 1 данное равенство истинно.

2) Предположим, что данное равенство истинно для n = k, т.е. что   1 + 3 + 5 + … + (2k – 1) =  k. Исходя из этого предположения, докажем, что оно истинно и для n = k + 1, т.е.  1 + 3 + 5 + … + (2k – 1) + (2(k + 1) – 1) =     (k + 1).

Рассмотрим левую часть последнего равенства.

По предположению, сумма первых k слагаемых равна  k и потому 1 + 3 + 5 + … + (2k – 1) + (2(k + 1) – 1) = 1 + 3 + 5 + … + (2k – 1) + (2k + 1)=

                                                                                    k

= k+ (2k + 1) =  k+ 2k + 1. Выражение  k+ 2k + 1 тождественно равно выражению (k + 1).

 Следовательно, истинность данного равенства для n = k + 1 доказана.

Таким образом, данное равенство истинно для n = 1 и из истинности его для n = k  следует истинность для n = k  + 1.

Тем самым доказано, что данное равенство истинно для любого натурального числа.

С помощью метода математической индукции можно доказывать истинность не только равенств, но и неравенств.

Задача. Доказать, что , где  nN.

Решение. Проверим истинность неравенства при n = 1. Имеем   - истинное неравенство.

Предположим, что неравенство верно при n = k, т.е.  - истинное неравенство. Докажем, исходя из предположения, что оно верно и при n = k + 1,т.е. (*).

Преобразуем левую часть неравенства (*), учитывая, что :   .

Но  , значит и .

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

Тем самым, используя аксиому 4, мы доказали, что данное неравенство истинно для любого натурального числа.

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

Задача. Доказать, что для любого натурального числа истинно утверждение  .

Решение. Проверим истинность утверждения при n = 1:  -истинное высказывание.

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

Преобразуем выражение: . Найдем разность k и k+1 членов. Если  окажется, что полученная разность      кратна 7, а по предположению вычитаемое делится на 7, то и уменьшаемое также кратно 7:

.

Произведение  кратно 7, следовательно, и .

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

Тем самым доказано, что данное утверждение истинно для любого натурального числа.

         Задача. Доказать, что для любого натурального числа n  2 истинно утверждение (7- 1)24.

Решение. 1) Проверим истинность утверждения при n = 2: - истинное высказывание.

2) Предположим, что данное нам утверждение истинно при n = k:         (7- 1)24.

Докажем, что оно верно и для n = k + 1, т.е. (7- 1)24. Преобразуем наше утверждение:  (7- 1)24 = 7- 1 = 7- 1 = 7(48 + 1) – 1 = 7 48 + (7- 1).

Так как 7 48 делится на 24, а выражение (7- 1) делится на 24 по нашему предположению, то по теореме о делимости суммы имеем, что 7 48 + (7- 1) и (7- 1)24.

         Мы показали, что данное выражение кратно 24 при n = 2, и из того, что оно кратно 24 при n = k, следует, что оно кратно 24 и при n = k + 1.

Значит данное утверждение (7- 1)24 истинно при любом натуральном n.