Министерство образования и науки российской федерации

ФГБОУ ВПО

“Воронежский государственный УНИВЕРСИТЕТ

ИНЖЕНЕРНЫХ технологиЙ”

Кафедра информационных технологий,

моделирования и управления

ТЕОРИЯ МНОЖЕСТВ

Методические указания

к практическим занятиям

по дисциплине "Дискретная математика"

ВОРОНЕЖ

2012

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

Метод математической индукции – универсальный способ доказательства утверждений, зависящих от натурального аргумента n. Он основан на следующем принципе математической индукции: утверждение справедливо для любого натурального n, если:

1⁰ оно справедливо для n = 1;

2⁰ из того, что оно верно для всех n  k (k  1) следует его справедливость для n = k + 1.

Часто это утверждение следует предварительно выдвинуть в виде гипотезы на основе простого обобщения частных случаев. Однако индуктивное утверждение может быть неверным, простая индукция позволяет лишь выдвинуть гипотезу, которую надо доказать, например, с помощью математической (полной) индукции. Можно привести много примеров, когда простая индукция приводит к ошибочным выводам. Например, анализируя числа 1, 3, 5, 7 можно прийти к неверному заключению, что все нечетные числа являются простыми.

Задача 1. Найти сумму .

Решение. Имеем:;;;. Есть предположение, что. Докажем эту формулу.

1⁰. При n = 1 – формула верна.

2⁰. Предположим, что для произвольного k 1 для всех n k . В частности, дляn = k . Найдем. Имеем. По предположению это равно

= ==,

что и требовалось доказать.

Этот принцип, являющийся одной из аксиом натурального ряда можно перефразировать так: если в цепочке утверждений Р(n) первое утверждение Р(1) верно, а из справедливости Р(k) следует справедливость Р(k + 1), то вся цепочка состоит из верных утверждений.

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

Задача 2. Найти ошибку в следующем доказательстве, что все натуральные числа равны между собой.

Предположим, что k = k + 1. Прибавим по 1 к обеим частям этого равенства. Получим k + 1 = k + 2, что и требовалось доказать.

Решение. Ошибка этого “доказательства” состоит в отсутствии проверки утверждения при n = 1.

Задача 3. Доказать неравенство 2ⁿ > 2n + 1 при n  3.

Решение.

1⁰. 2³ > 7.

2⁰. 2^{k + 1} = 2×2^k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k – 1) > 2k + 3.

Задача 4. Обозначим H_n = 1 + 1/2 + 1/3 +…+ 1/n – гармонические числа. Доказать, что Н_n неограниченно сверху, т.е. что Н_n  + ().

Решение.

1⁰. m = 1, Н₂ = 1 += 1 +.

2⁰. > + + = > 1 + = 1 + .

Это означает, что при достаточно большом n значение Н_n может стать больше любого числа.

Задача 5. Доказать, что для любого n  0 число 11ⁿ⁺² + +12²ⁿ⁺¹ делится на 133.

Решение.

1⁰. 11² + 12¹ = 133 – верно при n = 0.

2⁰. 11^{k +3} + 12^{2(k + 1) +1} = 1111^{k + 2} + 14412^{2k + 1} = (144–133)  11^{k + 2} + 14412^{2k + 1} = 144  (11^{k + 2} + 12^{2k + 1}) – – 13311^{k + 2}.

В полученной разности уменьшаемое делится на 133 по предположению, а вычитаемое содержит множитель 133. Следовательно, все выражение делится на 133.

Задача 6. Доказать, что любую сумму денег более 7 копеек можно уплатить монетами достоинством 3 и 5 копеек.

Решение.

1⁰. 3 + 5 = 8 – верно.

2⁰. Пусть уплатили k копеек. Возможны два случая.

а) Вся сумма оплачена только 3-копеечными монетами, т.е. k=3n, где n3. Тогда k+1=3(n-3)+9+1=3(n-3)+25. В этом случае надо 9 копеек (3+3+3) заменить на 5 + 5.

б) Использована хотя бы одна 5-копеечная монета. Тогда надо 5 копеек заменить на 3 + 3 – снова получим сумму k + 1.