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

Метод математической индукции является одним из наиболее универсальных методов проведения матема­тических доказательств. Суть его заключается в следую­щем. Допустим, мы хотим доказать, что некоторое утверждение справедливо при любых значениях натурального числа П, содержащегося в формулировке этого утверж­дения. Например, что для любого натурального П справедливо следующее равенство:

(1)

Легко проверить, что эта формула дает правильный результат при N = 1, 2, 3, 4. Но невозможно ее прове­рить для Всех значений П, т. к. множество натуральных чисел бесконечно! Как же доказать, что утверждение верно для любых П, не проверяя этого непосредственно? Оказывается, что достаточно:

А) проверить данное утверждение при П = 1;

Б) предположив, что оно верно при П = K, доказать, что оно верно при N = K + 1. В этом и заключается метод математической индукции.

В рассматриваемом примере формула (1) при N = 1 дает , т. е. что сумма из одного слагаемого 1 равна единице. Таким образом, при П = 1 формула вер­на. Теперь предположим, что она верна при N = K, тогда справедливо равенство

.

Докажем, что формула (1) верна при П = K + 1, т. е.

.

Действительно, используя допущение, получаем

,

Что и требовалось доказать.

Рассмотрим еще один пример. Докажем, что при любом натуральном показателе степени N число 8N – 1 делится на 7.

Доказательство. Проверим условия а) и б). Подста­вим в выражение 8N – 1 вместо П число 1. Тогда значение этого выражения будет равно 8 – 1 = 7. Это число делится на 7, т. е. условие а) проверено. Теперь допустим, что 8K – 1 делится на 7. Покажем, что в таком случае 8K + 1 – 1 так­же делится на 7. Преобразуем последнее выражение так:

В результате преобразований мы получили сумму двух слагаемых, каждое из которых делится на 7. Дей­ствительно, первое слагаемое имеет множитель 7, а вто­рое делится на 7 по предположению индукции. Следова­тельно, сумма также делится на 7 и условие б) также проверено. Утверждение доказано.

Теперь докажем общее правило умножения (см. §1).

Теорема 1. Пусть требуется последовательно вы­полнить п действий, причем первое действие может быть выполнено т1 способами, второе — т2 способами и т. д. , наконец, п-е действие — тN способами. Обозна­чим через Sn Число всех способов, которыми можно вы­полнить п действий. Тогда

Sn= т1 • M2 • ... • Mn. (2)

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

При П = 1 мы получаем одно действие, которое мож­но выполнить Т1 способами. Произведение (2) состоит в этом случае также из одного сомножителя Т1. Следова­тельно, формула (2) при N = 1 верна.

Допустим, что формула (2) верна для П = K действий:

Sk = т1 • m2 • ... • Mk. (3)

Докажем, что она верна для П = K + 1 действий. Обозна­чим произвольный вариант выполнения K действий на­бором из K чисел. Например, набор (3, 1, 6, ..., 5) озна­чает вариант, в котором первое действие выполнено тре­тьим способом, второе действие — первым способом и так далее, наконец, K-E действие выполнено пятым способом. В случае, если выполняются K + 1 действий, каждый ва­риант записывается как набор из K + 1 чисел. Но всякий набор из K + 1 чисел получается добавлением одного чис­ла к какому-либо набору из K чисел. Например, из одного набора (3, 1, 6, ... , 5) можно получить такие:

(3, 1, 6, ..., 5, 1), (3, 1, 6, ..., 5, 2), ... , (3, 1, 6, .... 5, Mk+1),

Т. е. всего ТK+1 вариантов. Поэтому число всех способов выполнения K + 1 действий будет

Sk + 1 = Sk • mk+1 = M1 • m2 • ... • Mk • ТK +1.

Таким образом, условие б) индукции тоже выполняется. Теорема доказана.

УПРАЖНЕНИЯ

4. Абонент забыл две последние цифры номера телефона и набирает их наудачу. Каково наибольшее возможное число безуспешных попыток абонента?

5. Семеро терпеливых стоят в очереди в кассу. Сколькими способами можно составить очередь?

6. В колоде 36 карт. Наудачу вынимают 3 карты. Каково число всех возможных комбинаций? Сколько троек содержат по крайней мере один туз? Сколько тро­ек содержат только один туз? Сколько раз попадется комбинация дама—семерка—туз?

< Предыдущая		Следующая >