Принцип математической индукции

 

Выражение при первых 39 натуральных является простым числом, а при это не простое число. К доказательству справедливости утверждений, содержащих натуральный аргумент мы и переходим.

Принцип математической индукции (ПМИ) состоит в следующем: для справедливости любого утверждения , высказанного для всех натуральных чисел , достаточно:

1) доказать истинность ;

2) и доказать истинность импликации

На самом деле, из формулировки ПМИ следует, что область истинности предиката является индуктивным множеством (см. п. 1.2.), а значит, содержит множество натуральных чисел.

Здесь утверждение первого пункта называется базой, а второго – индуктивным переходом.

Замечание. Методом математической индукции можно доказывать утверждения, справедливые и при , где . В ходе доказательства надо заменить первый шаг: доказать утверждение при , а все остальное оставить, как и прежде, при необходимости пользуясь тем, что .

В качестве примера применения ПМИ докажем полезную для нас формулу бинома Ньютона.

Произведение натуральных чисел обозначим ( читается: эн-факториал). Будем считать .

В, частности, имеем , , , и т.д.

Теорема 1.6.1. Для любого натурального числа справедлива формула (формула бинома Ньютона)

.

(Коротко эту формулу можно записать так:

, где - биномиальный коэффициент.)

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

1. При формула верна: , поскольку

.

База получена.

2. Докажем, что, если , то

Сначала докажем вспомогательное утверждение о биномиальном коэффициенте: при имеем

.

Действительно,

.

Далее, получаем

Индуктивный переход является истинным.

Значит, теорема доказана. o

Замечание. Подобным образом доказывается и формула для полинома Ньютона от неизвестных вида

,

где - целые положительные числа.

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

Каждый внутренний элемент этой таблицы получается как сумма элементов, стоящих левее и правее строкой выше.

Рассмотрим некоторые свойства биномиальных коэффициентов, которые хорошо просматриваются в треугольнике Паскаля:

1) свойство, используемое при построении треугольника Паскаля:

;

2) количество элементов в строке (в разложении бинома степени n) на единицу больше показателя степени бинома;

3) сумма биномиальных коэффициентов в любой строке равна 2 n, то есть ;

4) , так как

Это свойство означает, что таблица Паскаля симметрична относительно своей центральной линии, или, другими словами, равноотстоящие от краев элементы строки одинаковы: нулевой элемент равен последнему ; первый элемент равен предпоследнему и т.д.

5) Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетныx местах;

6) каждый элемент строки равен предшествующему, умноженному на коэффициент, равный , то есть . В самом деле,

При изложении теории пределов последовательности нам потребуется приводимое ниже неравенство Бернулли.

Теорема 1.6.2. При , и при целом справедливо неравенство (неравенство Бернулли) .

Доказательство (по индукции).

1) Сначала убедимся, что при неравенство является верным. Действительно, .

2) Докажем индуктивный переход:

, где .

На самом деле

Теорема 2 доказана. o