Лекции и упражнения

Глава 3
Метод математической
индукции.
Определение 23. Методом математической индукции называется способ
доказательства утверждений, состоящий в следующем: пусть есть некото-
рое утверждение
U
(
n
)
, зависящее от
n
?
N
и надо доказать это утверждение
для всех
n
?
N
. Доказательство состоит из двух этапов:
1. База индукции. Докажем утверждение
U
(1)
.
2. Шаг индукции. Докажем, что из утверждений
U
(1)
,
U
(2)
, . . . ,
U
(
n
?
?
1)
следует утверждение
U
(
n
)
.
Доказательство (корректности метода математической индукции).
Предположим обратное, пусть
U
(
n
)
верно не при всех
n
?
N
. Тогда найдет-
ся наименьшее
n
0
,
при котором утверждение неверно. Номер
n
0
не может
равняться 1, это следует из базы индукции. Следовательно, утверждения
U
(1)
,
U
(2)
, . . . ,
U
(
n
0
?
1)
верны, а из них и вытекает
U
(
n
0
)
.
Далее приводятся примеры использования метода математической ин-
дукции.
3.1 ѕХанойские башниї
Рассмотрим использование принципа математической индукции на приме-
ре игры ѕХанойские башниї. Это старинная игра, которая заключается в
следующем: На подставке укреплены три стержня. На левый стержень на-
низано несколько колец разного размера, внизу самое большое кольцо, на
нем поменьше, сверху еще меньше и т. п. Правила игры таковы:
1. За один ход можно переносить только одно кольцо.
2. Любое кольцо можно укладывать либо на большее кольцо, либо на
свободный стержень, т.е. запрещено укладывать большее кольцо на
меньшее.
33

34
ГЛАВА 3. ИНДУКЦИЯ
Каково наименьшее число ходов необходимо для того, чтобы перенести все
кольца с левого стержня на правый (при этом средний стержень использу-
ется как вспомогательный)?
Поиграв немного с различным числом колец, можно заметить, что с од-
ним кольцом головоломка решается за 1 ход, с двумя  за 3 хода, с тремя 
за 7, с четырьмя  за 15 и.т.д. Логично предположить, что число ходов для
n
колец на единицу меньше
n
й степени двойки. Но как это проверить для
всех значений
n
? Их же бесконечно много! На помощь приходит метод ма-
тематической индукции:
Утверждение 1. Головоломку с
n
кольцами можно решить за
2
n
?
1
ходов и нельзя  за меньшее число ходов.
Доказательство.
Будем доказывать индукцией по
n
:
База индукции. База индукции очевидна, головоломка с 1 кольцом реша-
ется за 1 ход  просто перекладываем кольцо с первого стержня на третий.
Шаг индукции. Сделаем шаг индукции. Пусть для
n
?
1
кольца задача
решается за
2
n
?
1
?
1
ходов. Тогда,очевидно, можно переложить кольца с
1го по
n
?
1
е за столько же ходов на второй стержень; затем переложить
n
е кольцо на третий стержень, а потом, опять за
2
n
?
1
?
1
ходов переложить
кольца с 1го по
n
?
1
е со второго стержня на третий. Всего получается
(2
n
?
1
?
1) + 1 + (2
n
?
1
?
1) = 2
n
?
1
ходов.
За меньшее число ходов головоломку решить нельзя, поскольку, как
бы мы не перекладывали кольца, надо в какой-то момент переложить
n
-е
кольцо с первого стержня на третий, а это возможно, только в случае, когда
все остальные кольца лежат на втором стержне.
3.2 Неравенство Бернулли
Теорема 4 (Неравенство Бернулли). Пусть
x >
?
1
и
x
6
= 0
;
n
?
N
\ {
1
}
.
Тогда
(1 +
x
)
n
>
1 +
nx
.
Доказательство.
Докажем индукцией по
n
.
База индукции. Очевидно
(1 +
x
)
2
= 1 + 2
x
+
x
2
>
1 + 2
x
.
Шаг индукции. Пусть
n
>
1
. По предположению индукции
(1 +
x
)
n
?
1
>
1 + (
n
?
1)
x.
Умножим обе части этого неравенства на
1 +
x >
0
.
Тогда
(1 +
x
)
n
>
(1 + (
n
?
1)
x
) (1 +
x
) = 1 +
nx
+ (
n
?
1)
x
2
>
1 +
nx.
Следствие 1. При любых
?, ? >
0
,
?
6
=
?
и
n
?
N
выполнено неравенство
?
n
+1
+
n
·
?
n
+1
>
(
n
+ 1)
·
??
n
.

3.3. ФОРМУЛА ВКЛЮЧЕНИЙИСКЛЮЧЕНИЙ.
35
Доказательство.
Обозначим
?
?
= 1 +
x
, тогда по неравенству Бернулли
?
?
n
+1
>
1 + (
n
+ 1)
x
= (
n
+ 1)
?
?
?
n.
Умножим обе части на
?
n
+1
, получим
?
n
+1
>
(
n
+ 1)
·
??
n
?
n
·
?
n
+1
.
Перенося
n
·
?
n
+1
влево, получим требуемое неравенство.
3.3 Формула включенийисключений.
Докажем формулу включенийисключений (теорема 1): Доказательство.
|
A
1
?
. . .
?
A
n
|
=
X
1
?
i
?
n
|
A
i
| ?
X
1
?
i?
n
|
A
i
?
A
j
|
+
+
X
1
?
i?
n
|
A
i
?
A
j
?
A
k
| ?
. . .
+ (
?
1)
n
?
1
|
A
1
?
A
2
?
. . .
?
A
n
|
.
Доказательство будем вести индукцией по
n
.
База индукции. При
n
= 2
представим
A
1
?
A
2
= (
A
1
\
A
2
)
?
(
A
1
?
A
2
)
?
?
(
A
2
\
A
1
)
, причем три множества, стоящие в правой части не пересекаются.
Поэтому
|
A
1
?
A
2
|
=
|
A
1
\
A
2
|
+
|
A
1
?
A
2
|
+
|
A
2
\
A
1
|
=
=
|
A
1
| ? |
A
1
?
A
2
|
+
|
A
1
?
A
2
|
+
|
A
2
| ? |
A
1
?
A
2
|
=
|
A
1
|
+
|
A
2
| ? |
A
1
?
A
2
|
,
что и доказывает утверждение при
n
= 2
.
Шаг индукции. Предположим, что утверждение доказано для
n
?
1
, обо-
значим
B
=
A
1
?
A
2
?
. . .
?
A
n
?
1
и
B
0
=
B
?
A
n
= (
A
1
?
A
n
)
?
(
A
2
?
A
n
)
?
?
. . .
?
(
A
n
?
1
?
A
n
)
. Тогда, применяя предположение индукции к
A
n
и
B
,
получим
|
A
1
?
A
2
?
. . .
?
A
n
|
=
|
B
?
A
n
|
=
|
B
|
+
|
A
n
| ? |
B
0
|
.
(3.3.1)
Заметим, что для
B
и
B
0
тоже можно применить утверждение теоремы, т.к.
каждое из них содержит объединение
n
?
1
множества. Получаем, что
|
B
|
=
X
1
?
i
?
n
?
1
|
A
i
| ?
X
1
?
i?
n
?
1
|
A
i
?
A
j
|
+
+
X
1
?
i?
n
?
1
|
A
i
?
A
j
?
A
k
| ?
. . .
+ (
?
1)
n
?
2
|
A
1
?
A
2
?
. . .
?
A
n
?
1
|

36
ГЛАВА 3. ИНДУКЦИЯ
|
B
0
|
=
X
1
?
i
?
n
?
1
|
A
i
?
A
n
| ?
X
1
?
i?
n
?
1
|
A
i
?
A
j
?
A
n
|
+
+
X
1
?
i?
n
?
1
|
A
i
?
A
j
?
A
k
?
A
n
| ?
. . .
+ (
?
1)
n
?
2
|
A
1
?
A
2
?
. . .
?
A
n
?
1
?
A
?
n
|
Подставив полученные выражения в 3.3.1 и заметив, что члены содержащие
нечетное число множеств идут со знаком ѕ+ї, а четное  со знаком ѕї,
получаем требуемое равенство.
3.4 Треугольник Паскаля.
Рассмотрим треугольник, составленный из чисел по следующим правилам:
•
В первом ряду одно число 
1
.
•
В каждом следующем ряду чисел на одно больше, чем в предыдущем.
•
В каждом ряду крайние числа равны 1.
•
Начиная с третьего ряда каждое число равно сумме двух своих сосе-
дей: сверхуслева и сверхусправа.
Эту конструкцию называют треугольником Паскаля (см. рис. 3.4).
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
. . .
. . .
. . .
Рис. 3.1: Треугольник Паскаля.
Утверждение 2. Число, стоящее в
n
+ 1
ряду на
k
+ 1
месте можно
найти по формуле
C
k
n
=
n
!
k
!(
n
?
k
)!
,
где числа
C
k
n
 число сочетаний из
n
элементов по
k
широко используются в комбинаторике.

3.4. ТРЕУГОЛЬНИК ПАСКАЛЯ.
37
C
0
0
C
0
1
C
1
1
C
0
2
C
1
2
C
2
2
C
0
3
C
1
3
C
2
3
C
3
3
C
0
4
C
1
4
C
2
4
C
3
4
C
4
4
Рис. 3.2: Биномиальные коэффициенты.
Доказательство.
Проведем индукцию по номеру ряда.
База индукции. Для
n
= 1
получим
C
0
0
=
0!
0!0!
= 1
.
Шаг индукции. Пусть предположение индукции верно для
n
ряда. До-
кажем его для
n
+ 1
го Для крайних элементов получим:
C
0
n
=
n
!
0!
n
!
= 1
;
C
n
n
=
n
!
n
!0!
= 1
. Для остальных по предположению индукции сумма соседей
сверху равна
C
k
?
1
n
?
1
+
C
k
n
?
1
=
(
n
?
1)!
(
k
?
1)!(
n
?
k
)!
+
(
n
?
1)!
k
!(
n
?
1
?
k
)!
=
=
(
n
?
1)!
·
k
k
!(
n
?
k
)!
+
(
n
?
1)!
·
(
n
?
k
)
k
!(
n
?
k
)!
=
(
n
?
1)!
·
n
k
!(
n
?
k
)!
=
n
!
k
!(
n
?
k
)!
=
C
k
n
.
Замечание. Попутно было доказано тождество
C
k
?
1
n
?
1
+
C
k
n
?
1
=
C
k
n
. Оно нам
позднее понадобится

38

жүктеу/скачать 1,95 Mb.

Достарыңызбен бөлісу: