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

ГОУВПО

“Воронежская государственная технологическая академия”

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

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

ДИСКРЕТНАЯ МАТЕМАТИКА

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

по дисциплине "Математика",

раздел "Дискретная математика"

Для специалистов и бакалавров,

Обучающихся по направлениям

230400 – "Информационные системы и технологии",

230700 – "Прикладная информацика"

Дневной и сокращенной формы обучения

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

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

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

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

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

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

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

= = = ,

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

Задача 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. Доказать, что для любого n ³ 0 число 11^{n + 2} + 12^{2n + 1} делится на 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.