Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

(2)

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

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

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

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

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

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

,

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

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

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

8 k +1 - 1 = 8 k +1 - 8 k + 8 k - 1 = 8 k (8 - 1) + (8 k - 1) = = 8 k 7 + (8 k - 1).

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

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

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

Sn = m1 • m2... • тп. (2)

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

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

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

Sk = m1 • т2 •... • mk. (3)

Докажем, что она верна для п = k + 1 действий. Обозначим произвольный вариант выполнения k действий набором из k чисел. Например, набор (3, 1, 6,..., 5) означает вариант, в котором первое действие выполнено третьим способом, второе действие — первым способом и далее, наконец, k -е действие выполнено пятым способом. В случае, если выполняются 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 = S k • m k+1 = m1 • m2 •... • mk • mk +1.

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





Дата публикования: 2015-03-26; Прочитано: 272 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...