§ 6. Принцип математической индукции.
Для доказательства различных высказываний P(n), зависящих отnN, применяется принцип математической индукции.
Индукция – это переход от частного к общему.
Определение. МножествоА Rназывается индуктивным, если: 1) 1А, 2)хА(х+ 1)А.
Вставка 1.
Исходя из понятия индуктивного множества, можно дать следующее определение натурального числа: число nRназывается натуральным, если оно является элементом любого индуктивного множества.
Отсюда сразу следует, что 1 N, а также еслиnN, то (n + 1)N. Действительно, возьмем произвольное индуктивное множествоА. ЕслиnN, тоnА. Тогда (n+ 1)А. А т.к. множествоА- произвольно, то (n+ 1)N.
Таким образом, N– индуктивное множество, причем наименьшее из всех индуктивных множеств (в смысле принадлежности всем индуктивным множествам).
Теорема (Принцип математической индукции). Пусть дано высказываниеP(n),nN. Предположим, что 1) высказывание Р(1) истинно, 2) если истинноP(n), то истинно также
P(n+1). Тогда высказываниеP(n) является истиннымn N.
Доказательство. ПустьМN– множество натуральных чисел, для которых высказываниеP(n) является истинным. Тогда 1М. в силу условия 2) изnМследует (n+ 1)М. Это означает, что множествоМиндуктивно, т.е.МN. А т.к.МN, тоМ=N, т.е. множество техn, для которыхP(n) истинно, совпадает сN. Таким образом,P(n) истинноnN.
При доказательстве методом математической индукции используется следующая терминология: высказывание Р(1) - истинно – основание индукции;P(n) - истинно –индукционное допущение;P(n+1) – истинно –индукционный переход.
Вставка 2.
Вопросы и упражнения.
В чем состоит принцип математической индукции?
Какие из перечисленных множеств являются индуктивными: а) Z, б)N, в)N{0}, г)
?Доказать равенство 1 + 2 + … + n =
.Доказать обобщение неравенства Бернулли
,
где
-
вещественные числа одного знака и
большие – 1.Доказать формулу бинома Ньютона
,
где
- число сочетаний изnпоk.Доказать, что любое индуктивное множество неограниченно сверху.
Докажите неравенство |x1+x2+ ...+xn||x1| + |x2| + ...+ |xn|.