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

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

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

2) предположив, что оно верно при N = K, доказать, что оно верно при N = K + 1.

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

(1)

Убедимся, что при N = 1 оно верно: .

Предположим, что формула (1) верна при N = K: .

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

Используя допущение, получим:

,

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

Другой пример. Докажем, что при любом натуральном показателе степени N число делится на 7.

Проверим при N = 1, получим: 81 – 1 = 7, т. е. делится на 7.

Допустим, что 8k – 1 делится на 7. Покажем, что в этом случае 8k+1 – 1 также делится на 7:

8k+1 – 1 = 8k+1 + 8k – 8k – 1 = 8k(8 – 1) + (8k – 1) = 7×8k + (8k – 1)

Это сумма двух чисел, каждое из которых делится на 7, следовательно, утверждение доказано.

Теорема 1. Пусть требуется последовательно выполнить N действий, причем первое действие может быть выполнено M1 способами, второе – M2 способами и т. д., наконец, N-Е действие – Mn способами. Тогда число Sn всех способов, которыми можно выполнить N действий, равно:

(2)

Доказательство. При N = 1 получаем одно действие, которое можно выполнить M1 способами. Значит, при N = 1 верно. Пусть формула (2) верна для N = K действий:

(3)

Докажем, что она верна для N = K + 1 действий.

Обозначим произвольный вариант выполнения K действий набором из K чисел. Например, набор (3,1,6,…,5) означает вариант, в котором первое действие выполняется третьим способом, второе – первым способом и т. д., K - е действие – пятым способом. В случае выполнения K + 1 действия каждый из вариантов описывается K + 1 числом. Всякий такой набор получается добавлением одного числа к какому – либо набору из K чисел, например:

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

Всего Mk+1 вариантов. Число всех способов выполнения K + 1 действий будет

,

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

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