§ 9. Различные виды доказательств по индукции Усиленный принцип полной математической индукции

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

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

Т(п) верно для п=1,m.e. Т(1) истинно;

каково бы ни было натуральное число т, из предположения о том, что Т(п) истинно для всех п < т, следует, что оно верно и для т, т. е. Т (т) истинно.

Доказательство от противного. Предположим, что Т(п) верно не для всякого натурального числа. Тогда множество А всех натуральных чисел, для которых Т(п) не верно, не пусто и имеет наименьший элемент, который обозначим через т. По условию 1) т≠1, следовательно, существуют натуральные числа, меньшие т. Так как т — наименьший элемент в А, то все натуральные числа, меньшие т, уже А не принадлежат, а значит, для них утверждение T(n) верно. Но тогда по условию 2) оно должно быть верно и для т — пришли к противоречию. Остается принять, что А = 0. Но это означает, что Т(п) верно для любого натурального числа.

Обобщенный принцип полной математической индукции

Иногда истинность утверждения Т(п) нужно доказать для всех натуральных чисел, начиная с некоторого натурального числа а. Тогда используется следующая теорема.

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

1) предложение Т(п) верно для п=а, т.е. Т(а) истинно;

2) каково бы ни было натуральное число п > а, из предположения о том, что Т(п) истинно, следует, что Т(п') истинно.

Доказательство. Обозначим через М множество, содержащее все натуральные числа, меньшие а, и все n, для которых Т(п) истинно. Пользуясь принципом полной математической индукции, докажем, что п М для любого п N. По условию 1) а М, а так как 1 ≤ а, то 1 М. Пусть п М, тогда либо п < а, либо Т(п) истинно. В первом случае п' ≤ а, откуда п' М, а во втором — по условию 2) п' М. Таким образом, М = N. Отсюда следует истинность Т(п) для любого n ≥ а.

Обобщенный усиленный принцип полной математической индукции

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

Теорема 3. Пусть а N. Предложение Т(п) верно для любого натурального числа п ≥ а, если выполнены следующие условия:

предложение Т(п) верно для п = а, т.е. Т (а) истинно;

каково бы ни было натуральное число т ≥ а, из предположения о том, что Т(п) истинно для всех натуральных п таких, что а≤п<т, следует истинность T(m).

Доказательство. Обозначим через М множество, содержащее все натуральные числа, меньшие а, и все п, для которых Т(п) истинно. Пользуясь усиленным принципом полной математической индукции, нетрудно доказать, что всякое натуральное число принадлежит М. Это и доказывает теорему.

§ 10. Вычитание и деление натуральных чисел

Теорема 1. Сумма любых двух натуральных чисел боль­ше каждого из слагаемых (или каждое слагаемое меньше суммы).

Доказательство. Пусть х и у — любые натураль­ные числа, x + y = z — натуральное число, их сумма: она существует и определена слагаемыми однозначно. Отсюда, по определению знака > и следует теорема:

z = x + y > x, z = x + y > y Ч. т. д.

Следствие 1. Если натуральное число z меньше или равно натуральному числу y, z ≤ y, то не существует такого натурального числа х, для которого x + y = z.

Следствие 2. Если натуральное число z больше натурального числа y, z > y, то существует такое натуральное число х, для которого x + y = z.

Доказательство. Если z > y, то z = y + u, где и — требуемое натуральное число х. Ч. т. д.

Определение 1. Натуральное число х, удовлетво­ряющее равенству x + y = z, называется разностью на­туральных чисел z и у и обозначается z - y = x, (z — уменьшаемое, у — вычитаемое), а действие, которое дает разность, называется вычитанием.

Вычитание обратно сложению, так как представляет нахождение одного из слагаемых, когда известны сумма и второе слагаемое. Так как сложение коммутативно, то безразлично, какое из слагаемых — первое или второе — неизвестно.

Теорема 2. Если и z — натуральные числа, то для существования разности z – у необходимо и достаточно, чтобы выполнялось неравенство z > y .

Доказательство. Если существует разность z – у = x, то это значит, что x + y = z и z > y. И наоборот, если z > y, то z = y + x, где х — натуральное число, т. е. разность z – у = x существует. Ч. т. д.

Следствие. Если существует разность натураль­ных чисел, то эта разность единственна.

Доказательство. Допустим, что существует разность двух чисел z и у, имеющая два значения х1 и х2:

z – у = x1, z – у = x2, т.е. x1 + y = z, x2 + y = z,

следовательно, x1 + y = x2 + y отсюда x1 = x2. Ч. т. д.

Теорема 3. Если х ≠ 1 — натуральное число, то любое натуральное число удовлетворяет неравенству у < ху (1).

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

При у = 1, 1 < x∙1 = x и так как х ≠ 1 то это неравенство верно.

Пусть имеет место неравенство y < xy. Докажем, что это неравенство верно для y′: Действительно, ху′ = ху + х > у + х > y+1 = y′, т. е. y′< ху′.

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

Теорема 4. Если натуральное число х меньше натурального числа у, х < у, то не существует такого натурального числа z, что х = yz.

Доказательство. Допустим, что число z суще­ствует, т. е. выполняется равенство х = yz, тогда возмож­ны два случая: z = 1 и z ≠ 1. Пусть z = 1 но тогда x = y∙1 = y, что противоречит условию теоремы: x < y.

Пусть теперь z ≠ 1, тогда 1 < z и так как x < y, то x < yz, что противоречит допущению х = yz. Следовательно, не существует натурального числа z такого, что при условии x < y имеет место равенство х = yz. Ч. т. д.

Следствие. Если х и у — натуральные числа, то для того, чтобы, существовало натуральное число z, удовлетворяющее равенству х = yz, необходимо, чтобы х ≥ y.

Однако это условие не будет достаточным. Например, х=5, у=3, т. е. х > y, но не существует натурального числа z такого, чтобы 3∙z=5.

Определение 2. Натуральное число z, удовлетворяющее равенству между натуральными числами x=yz, называется частным и обозначается: z = x:y = , так что x = y· . Действие по которому находится частное, называется делением, оно обратно умножению.

Теорема 5. Если частное натуральных чисел существует, то оно единственное.

Доказательство. Пусть yz1 = x и yz2 = x. Тогда yz1 = yz2, отсюда z1 = z2. Ч. т. д.

Если частное двух чисел х и у существует, то говорят, что х делится на у.

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