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

Пусть множество M R таково, что: 1) 1 M; 2) каково бы ни было натуральное число n M, то и число n+1 M (таким образом, N M). Тогда, при выполнении условия M N следует, что М = N.

Следовательно, если мы установим, что утверждение A (x) справедливо при x = 1, и, если из того, что A(x) справедливо при произвольном k N, вытекает его справедливость при k + 1, то утверждение A(x) будет верно при всех n N.

Доказательство, основанное на принципе математической индукции, называется доказательством методом математической индукции. Такое доказательство состоит из двух частей (из доказательства двух самостоятельных теорем):

Теорема 1. Утверждение справедливо для n = 1.

Теорема 2. Если утверждение справедливо для некоторого натурального числа n, то оно справедливо для n + 1 .

Если обе эти теоремы доказаны, то на основании принципа математической индукции утверждение справедливо для всякого натурального n .

Пример 1. Доказать, что

S_n = + + + …+ = .

Теорема 1. Для n = 1 гипотеза верна, так как S₁ = = .

Теорема 2. Предположим, что гипотеза верна для n = k, т. е. что

S_k = + + + …+ = .

Докажем, что тогда гипотеза обязана быть верной и для n = k + 1, т.е. что S_k+1 = .

Действительно, S_k+1 = S_k + , следовательно, по условию теоремы,

S_k+1 = + = .

Обе теоремы доказаны. Теперь на основании принципа математической индукции мы имеем право утверждать, что S_n = при всяком натуральном n.

Замечание 1. Необходимо подчеркнуть, что доказательство методом математической индукции, безусловно, требует доказательства обеих теорем 1 и 2.

Решая пример 1, мы выдвинули гипотезу S_n = , которая (как было доказано выше) оказалась верной.

Интересно рассмотреть случай «неверной гипотезы»:

S_n = . (2)

При n = 1 формула (2) верна, так как S₁ = .

Предположим, что формула (2) верна при n = k, т. е. S_k = и вычислим S_{k+1 :}

S_k+1 = + = + = .

Вычисленное значение S_k+1 отлично от требуемого ( S_k+1 = ), т.е. из справедливости формулы (2) при n = k не следует её справедливость при n = k + 1.

Замечание 2. Если рассматриваемое утверждение верно не только при n = 1, но и в целом ряде частных случаев, то это еще не означает, что утверждение справедливо при всех n N. Действительно, рассмотрим функцию :

Вычислим несколько первых значений этой функции: . Наблюдательный читатель сразу заметит, что полученные числа ( 43, 47, 53, 61, 71, 83, 97) являются простыми числами (т.е. такими, которые делятся без остатка только на 1 и на себя). Продолжим вычисления: . Числа 113, 131 и 151 так же являются простыми и вполне естественно возникновение гипотезы: «Для любого натурального числа n число является простым числом».

Более того, большинство читателей абсолютно уверено, что обозначенная гипотеза уже доказана. Хотя простая проверка разрушает это предположение.

Рассмотренный пример позволяет сделать простой и в то же время важный вывод: Если утверждение справедливо в целом ряде частных случаев, то это не означает, что оно справедливо всегда.

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

Примеры с решениями

Пример 2. Вычислить сумму первых n нечётных чисел.

Решение. Обозначим искомую сумму S_n, т. е.

S_n = 1 + 3 + 5 + 7 +…+ ( 2n - 1).

Придаём n последовательно значения 1, 2, 3, ... до тех пор, пока у нас не накопится достаточно материала, чтобы на основе его построить более или менее надёжную гипотезу. Имеем

S₁ = 1, S₂ = 4, S₃ = 9, S₄ = 16, S₅ = 25, S₆ = 36.

Теперь всё зависит от наблюдательности решающего задачу и от его способности за частными результатами увидеть общий.

Полагаем, что в данном случае легко заметить, что

S₁ = 1², S₂ = 2² , S₃ = 3² , S₄ = 4² , S₅ = 5².

На основе этого можно предположить, что S_n = n².

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

Теорема 1. При n = 1 гипотеза справедлива, т.к. S₁ = 1 = 1².

Теорема 2. Допустим, что гипотеза верна для n = k, т.е. S_k = k². Докажем, что тогда гипотеза должна быть верна и для n = k + 1, т.е. S_k+1 = (k + 1)².

Действительно,

S_k+1 = S_k + (2k + 1) = k² + (2k + 1) = (k + 1)²,

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

Пример 3. Доказать, что сумма n первых чисел натурального ряда равна .

Решение. Эта задача отличается от предыдущих задач тем, что гипотезу здесь строить не надо, она дана. Нужно только доказать, что гипотеза верна.

Обозначим искомую сумму S_n, т. е. S_n = 1 + 2 + 3 + 4 +…+ n.

Теорема 1. При n = 1 гипотеза верна.

Теорема 2. Пусть S_k = 1 + 2 + 3 + 4 +…+ k = . Покажем, что S_k+1 = . Действительно,

S_k+1 = S_k + (k + 1) = + (k + 1) = .

Задача решена.

Пример 4. Доказать, что сумма кубов трёх последовательных натуральных чисел делится на 9.

Решение. Сумма 1³ + 2³ + 3³ делится на 9. Значит, утверждение справедливо, когда первым из трёх последовательных натуральных чисел является 1.

Пусть сумма k³ + (k + 1)³ + (k + 2)³, где k - некоторое натуральное число, делится на 9. Выражение

(k + 1)³ + (k + 2)³ + (k + 3)³ = (k + 1)³ + (k + 2)³ + k³ + 9k² + 27k + 27 =

= [k³ + (k + 1)³ + (k + 2)³] + 9 (k² + 3 + 3)

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

Задачи для самостоятельного решения

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

S_n= 1 + 2 + 2² + 2³ +… +2^n-1.

Задача 2. Доказать, что для каждого натурального n верно равенство

1  2 + 2  5 +…+ n  (3n-1) = n²  (n + 1).

Задача 3. Доказать, что для каждого натурального n верно равенство

1² + 2² + 3² +…+ n² = .

Задача 4. Доказать, что для каждого натурального n верно равенство

1² + 3² + 5² +…+ (2n-1)² = .

Задача 5. Доказать, что для каждого натурального n верно равенство

1  2 + 2  3 + 3  4 +…+ (n - 1)  n = .

Задача 6. Доказать, что для каждого натурального n верно равенство

1³ + 2³ + 3³ +…+ n³ = .

Задача 7. Доказать, что при каждом натуральном n число 5  2^3n-2 + 3^3n-1 делится на 19.

Задача 8. Доказать, что при каждом натуральном n число n (2 n² - 3n + 1) делится на 6.

Задача 9. Доказать, что при каждом натуральном n число n⁵ – n делится на 5.

Задача 10. Доказать, что для каждого натурального n верно равенство

+ + …+ = .

Задача 11. Доказать, что для каждого натурального n верно равенство

+ + + …+ = .

Задача 12. При каких натуральных n справедливо неравенство 2ⁿ > n² ?

Задача 13. Доказать неравенство: (неравенство Бернулли).

Задача 14. Доказать, что

Задача 15. Доказать, что