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

Метод математической индукции является важным способом доказательства математических утверждений. Этот способ используют в тех случаях, когда требуется доказать справедливость какого-либо утверждения относительно любого натурального числа n.

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

1) База индукции. Этот этап состоит в проверке справедливости утверждения для .

2) Индукционный переход. Этот этап состоит в выводе из

предположения о справедливости утверждения для  справедливости утверждения также и для .

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

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

    Примеры. 1) Докажем тождество

                    ,           (5.1)

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

База индукции. Пусть . Тогда утверждение (5.1), очевидно, верно.

Индукционный переход. Предположим, что (5.1) верно при :

                    .

Докажем, что оно верно также при :

        . (5.2)

Обозначим . Тогда (5.2) можно записать в виде:

               .                             (5.3)

Будем преобразовывать (5.3):

.

Заметим, что по формуле суммы арифметической прогрессии . Тогда , что, очевидно, верно.

Утверждение доказано.

2) Докажем методом математической индукции неравенство Бернулли: , для всех .

База индукции. Пусть . Тогда неравенство принимает вид: , что, очевидно, верно.

Индукционный переход. Предположим, что неравенство верно при :

. Докажем, что оно верно при : .

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

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

3) Докажем методом математической индукции, что множество, состоящее из n элементов имеет  подмножеств.

База индукции. Пусть . Рассмотрим множество A, состоящее из одного элемента. Оно содержит ровно два подмножества: пустое множество  и само множество A.

Индукционный переход. Рассмотрим множество A,состоящее из  элементов. Предположим, что содержит подмножеств. Выясним, как изменится количество подмножеств множества A при добавлении к нему нового элемента a. Каждое “новое” подмножество (т. е. содержащее новый элемент a) получается из некоторого “старого” подмножества (не содержащего элемента a). Таким образом соответствие между новыми и старыми подмножествами является взаимно однозначным. Значит с добавлением одного элемента к множеству A, количество его подмножеств удваивается. Следовательно, после добавления одного элемента к множеству количество его подмножеств оказывается равным .