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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение порядка на множестве натуральных чисел

О. Для натуральных чисел и говорят, что «меньше », и пишут , если существует натуральное число , что .

Говорят, что «меньше или равно », и пишут , если или .

Отношение, инверсное к отношению , обозначают символом , т.е. тогда и только тогда, когда .

Для отношения порядка выполняются следующие свойства:

1) система является вполне упорядоченным множеством, т.е. она линейно упорядочена и любое непустое подмножество множества натуральных чисел имеет наименьший элемент;

2) для любых натуральных чисел и , если , то (свойство дискретности);

3) отношение монотонно относительно сложения и умножения, т.е. для любых натуральных чисел , и тогда и только тогда, когда и .

4) свойство архимедовости: для любых натуральных чисел и найдется такое натуральное число , что .

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

Дата добавления: 2014-03-11; просмотров: 634; Нарушение авторских прав

Мы поможем в написании ваших работ!