Аксиома индукции и следствие из нее. Метод математической индукции

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

 

Аксиома индукции

Пусть Е – некоторое непустое подмножество множеств натуральных чисел. Тогда в множестве Е есть наименьший элемент.

Следствие из аксиомы индукции

Если имеется множество утверждений, каждому из которых приписано натуральное число (его номер) n = 1,2,..., P(1),P(2),P(3),…P(k),… и если доказано, что:

1) справедливо утверждение с номером 1 P(1) (База индукции);

2) из справедливости утверждения с любым номером k (k – натуральное) P(k) следует справедливость утверждения с номером k + 1 P(k+1)(Индукционный переход);

 

то тем самым доказана справедливость всех утверждений, т. е. любого утверждения с произвольным номером k (k-натуральное).

 

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

 

Доказательство:

Докажем методом от противного. Пусть в этой последовательности все-таки есть ложное утверждение. Обозначим через Е множество номеров ложных высказываний (по нашему предположению оно непусто). По аксиоме индукции в множестве Е есть наименьший элемент, обозначим его n₀. n₀≠1, т.к. Р(1) - истинно. n₀ – элемент Е, n₀≠1, тогда элемент n₀ – 1 принадлежит множеству натуральных чисел. Получаем: n₀ – 1 < n₀, n₀ = min E, тогда n₀ – 1 не принадлежит Е, т.е. P (n_0–1)- истинно, поэтому P (n₀) – истинно (поскольку по индукционному переходу для любого k из P(k) следует P(k+1)) Но n₀ –номер ложного утверждения. Тем самым получаем противоречие.

 

Математическую индукцию можно сравнить с бесконечным рядом костяшек домино. Свойство выстроенных в ряд домино состоит в том, что если опрокинуть одну костяшку, падает следующая. Пусть утверждение Р(n) состоит в том, что падает n-я костяшка. Опрокидывание первой костяшки домино обозначим Р(1), т.е. истинность Р(1) состоит в том, что первая костяшка падает. Поскольку каждая костяшка опрокидывает следующую, то из истинности Р(к) следует истинность Р(к + 1). Поскольку падают все костяшки, Р{n) истинно для каждого положительного целого числа n.

 

Замечание 7.5.

Может произойти так, что в последовательности Р(1), Р(2),…P(k),… первым истинным является не первое, а некоторое j-е. Тогда принцип индукции можно сформулировать следующим образом:

1)P(j) истинно (база индукции)

2)Для произвольного k≥j, если P(k) истинно, то истинно P(k+1)

Тогда P(n) истинно для всех n ≥j

То есть не обязательно начинать рассмотрение с к=1 (хотя чаще всего начинают как раз с к=0 или 1).

 

Пример 7.5.

 

Используя принцип индукции для целых чисел, нужно доказать, что для любого целого числа n ≥ 4 имеет место неравенство n! > 2ⁿ.

При использовании индукции по n, в данном случае нельзя начинать с n = 1, поскольку утверждение для n=1 неверно. Начальной точкой должно быть n = 4, т.к. утверждение неверно также для n = 2 и n = 3.

Таким образом, база индукции рассматривается для первого утверждения, соответствующего n=4

Р(n) — утверждение "n! > 2ⁿ".

Сначала докажем утверждение для n = 4. При n = 4 имеем 4! = 24 и

2⁴ = 16, так что 4! > 2⁴.

Индукционный переход:

По индуктивному предположению имеем k!> 2^k. Нам нужно доказать, что (k+1)> 2^k+1 метим, что желаемый результат можно получить, если умножить левую часть неравенства на (k+ 1), а правую — на 2. Поэтому, если мы покажем, что (k+1)>2, то получим k!> 2^k и (k+1) > 2 и сможем сделать вывод, что (k+1)!> 2^k+1. Поскольку k ≥ 4, то k > 2. Следовательно, (k+1)k! > 2 · 2k и (k+1)!> 2^k+1. Таким образом, n! > 2n для каждого n > 4.

 

 

Принцип Архимеда

Теорема 7.6(1)

 

Каково бы ни было действительное число а, существует такое натуральное число n, что

n > а.

Доказательство

Если бы утверждение теоремы не имело места, то нашлось бы такое число а, что для всех натуральных чисел n выполнялось бы неравенство n≤а, т. е. множество натуральных чисел N было бы ограничено сверху. Тогда существовала бы конечная верхняя грань:

Поскольку β — 1 < β, то в силу определения верхней грани (найдется такое натуральное число n, что n > β — 1, т. е. n + 1 > β, но n + 1 — также натуральное число: /, поэтому данное неравенство противоречит условию существования верхней грани.