3) Шаг индукции: докажем, что утверждение верно для n = k+1, т. е.
1 + 3 + 5 + ... + (2k — 1) + (2k + 1) = (k + 1)2
.
По предположению, сумма первых k слагаемых в левой части равенства равна k2. Значит, то, что требуется доказать, можно записать так:
k2 + (2k + 1) = (k + 1)2,
но это очевидно.
Пример 15. Доказать, что для любого натурального n число n3 + 5n делится на 6.
Доказательство. База индукции имеется: при n = 1 число n3 + 5n = 6 делится на 6. Предполагаем, что для некоторого k число k3 + 5k делится на 6. Используя это, постараемся доказать, что тогда и (k + 1)3 + 5(k + 1) делится на 6. Проведём преобразования:
(k + 1)3 + 5(k + 1) = k3 + 3k2 + 3k + 1 + 5k + 5 =
= (k3 + 5k) + (3k2 + 3k) + 6 = (k3 + 5k) + 3k(k + 1) + 6.
Первое слагаемое в этой сумме делится на 6 по предположению, второе слагаемое тоже делится на 6, так как из чисел k, k + 1 одно обязательно чётно. Значит, вся сумма делится на 6, что и требовалось доказать.
В качестве ещё одного примера докажем теорему о числе подмножеств конечного множества.
Теорема 4. Множество, состоящее из n элементов, имеет 2n различных подмножеств.
Доказательство. Применим индукцию по числу n. Если множество A = {а} состоит из одного элемента, то его подмножества — это 0, {а}. Их 2, поэтому теорема при n = 1 верна (база индукции). Предполагаем, что любое множество из k элементов имеет 2k подмножеств. Рассмотрим множество
A = {а1,а2,... ,ак,ак+1}.
Все его подмножества разделим на 2 вида. К первому виду отнесём подмножества, не содержащие ак+1. По предположению, таких подмножеств 2к. Остальные подмножества содержат ак+1, их количество также равно 2к, потому что каждое из них получается добавлением ак+1 к одному из подмножеств первого вида. Всего подмножеств множества A имеется:
2к + 2к = 2 x 2к = 2к+1,
что и требовалось доказать.
|