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

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

Теорема 1(принцип математической индукции). Если некоторое высказывание с переменным (одноместный предикат), определенное на множестве , удовлетворяет следующим условиям: ) истинно; ) для каждого из истинно следует, что истинно . Тогда истинно для любого натурального .

Д.: Докажем для множества . Через обозначим множество натуральных чисел из , для которых , т.е. . Из выполнимости условий ) и ) следует: а) ; б) для любого , если , то . Тогда по аксиоме индукции (6) следует , т.е. , для любого .

Аналогично доказывается для множества (докажите самостоятельно).

Доказательство по индукции состоит из двух этапов: 1) доказывается, что 1 (0) удовлетворяет условию , т.е. (база индукции); 2) доказывается, что для всякого из (достоверность индуктивного шага).

Приведем еще две теоремы без доказательств, относящихся к методу математической индукции.

Теорема 2 (усиленный принцип математической индукции). Если некоторое высказывание с переменным , определенное на множестве , удовлетворяет следующим условиям: ) истинно; ) для каждого из истинно следует, что истинно. Тогда истинно для любого натурального .

В доказательстве используется теорема 1. Докажите самостоятельно.

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

1) доказывается, что 1 (0) удовлетворяет условию , т.е. истинно (база индукции);

2) предполагается, что для всякого  истинно, и доказывается, что также истинно (справедливость индуктивного шага).

Теорема 3 (обобщенный принцип математической индукции). Если некоторое высказывание с переменной , определенное на множестве натуральных чисел , удовлетворяет следующим условиям: ) истинно, ; ) для каждого , где , истинно следует, что истинно, тогда истинно для любого натурального числа .

Доказательство обобщенным принципом математической индукции, как и выше, состоит из двух шагов:

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

2) предполагается, что для всякого , где , истинно, и доказывается, что также истинно (достоверность индуктивного шага).

Пример 1. Найти сумму первых нечетных чисел натурального ряда, т.е. , где , т.е. .

Решение. Иногда для нахождения предполагаемого результата пользуются так называемой неполной индукцией, т.е. находят значения искомого выражения для некоторых первых значений . Вычисляя непосредственно значения при и 3, будем иметь: . Учитывая, что , можно сделать предположение: . Для доказательства справедливости высказанного предположения воспользуемся индукцией.

) , база индукции верна;

) Пусть утверждение верно для произвольного , т.е. или . Докажем для . или . Таким образом, . По теореме 1 для любого .

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

Решение. Воспользуемся обобщенным принципом математической индукции:

) или и , база индукции верна. Отметим, что 8 – наименьшее число, для которого данное утверждение должно быть справедливым.

) Предположим, что требуемое соотношение справедливо для произвольного числа , где , т.е. существуют такие неотрицательные целые числа и , что справедливо равенство . Докажем справедливость утверждения для числа . Возможны два случая:

1) , тогда , где .

2) , т.к. , то наименьшее предполагаемое может быть не меньше 9, т.е. . Тогда , где .

Согласно теореме 3 справедливость данного утверждения доказана.

Исходя из аксиоматического определения множества натуральных чисел, можно доказать, что для сложения и умножения натуральных чисел выполняются все свойства этих операций, известные из школьного курса математики.