Rambler's Top100





6
1!1!...!22!11 lll
. (4)
3. Индуктивный переход: докажем (3) при
1ln
, используя (4),
то есть докажем, что
1!2!11!...!22!11 lllll
.
В самом деле,
!11!...!22!11 llll
!111!1 lll
1!212!1 lll
Пример 3
Доказать, что для любого
Nn
1154 n
n
делится на 9. (5)
Доказательство
1. Базис индукции: проверим (5) при
1n
. ЛЧ=4+15-1=18 делится
на 9.
2. Индуктивное предположение: допустим, (5) выполняется при
mn
, то есть
1154 m
m
делится на 9. (6)
3. Индуктивный переход: докажем (5) при
1mn
, используя (6),
то есть докажем, что
1)1(154
1
m
m
делится на 9.
)1543()1154(11515441)1(154
1 mmmm
mmm
.
Первая скобка делится на 9 по индуктивному предположению. Ос-
талось доказать, что второй слагаемый делится на 9, то есть надо дока-
зать, что
54
m
делится на 3. Это утверждение мы будем доказывать
методом математической индукции, то есть нам придется применять
"индукцию в индукции". При m=1 4+5=9 делится на 3. Допустим,
54
k
делится на 3. Докажем, что
54
1k
делится на 3, но
54
1k
kkk
4354544
. Первый слагаемый делится на три по ин-
дуктивному предположению, а второе очевидно. Таким образом, мы
доказали, что
54
m
делится на 3, а вместе с этим, что
1154 n
n
де-
лится на 9.
Теперь сформулируем несколько утверждений, эквивалентных
ММИ.
Теорема 2
Пусть множество
NA
обладает следующими свойствами.
1.
A1
.
2. Для любого
Nk
, если
Ak
, то
Ak 1
. Тогда
NA
.