МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
Это метод доказательства некоторого утверждения для любого натурального n, основанный на следующем принципе:
Если утверждение верно для n = 1 (базис индукции),
и из справедливости его для n = k (предположение индукции),
вытекает справедливость этого утверждения для n = k + 1 (индукционный шаг),
то оно верно для всех n.
Часто доказательство по индукции имеет форму «спуска»:
Если утверждение верно для n=1
и (при n>1) из справедливости его для всех k < n
следует справедливость для k = n,
то утверждение верно для всех n.
Замечание!
Иногда удобно начать индукцию не с n = 1, a c n = 0 или с некоторого n = n0.
Принцип индукции эквивалентен аксиоме:
«В любом множестве натуральных чисел есть наименьшее»
ОБРАЗЦЫ РЕШЕНИЯ ЗАДАЧ
ЗАДАЧА 1
Доказать, что 12 + 22 + 32 + …+ n2 = 
для любого натурального n.
Доказательство:
1. Базис индукции
Проверим справедливость утверждения при n = 1.
, 
, 1 = 1 – верно.
2. Предположение индукции
Предположим, что утверждение верно при n = k, т. е. справедливо равенство
12 + 22 + 32 + …+ k2 = 
.
3. Индукционный шаг
Докажем, что утверждение верно и при n=k+1, т. е.
12 + 22 + 32 + …+ k2 + (k + 1)2 = 
.
Действительно, 12 + 22 + 32 + …+ k2 + (k + 1)2 = 
+ (k + 1)2 = =
Таким образом, доказана справедливость утверждения
12 + 22 + 32 + …+ n2 = для любого натурального n.
ЗАДАЧА 2
Доказать, что (32n+1 + 40n – 67) : 64 при любом натуральном n.
Доказательство:
1. Базис индукции
Проверим справедливость утверждения при n = 1.
(32×1+1 + 40×1 – 67) = 27 + 40 – 67 = 0,
0 : 64 – верно.
2. Предположение индукции
Предположим, что утверждение верно при n = k,
т. е. справедливо (32k+1 + 40k – 67) : 64
3. Индукционный шаг
Докажем, что утверждение верно и при n = k + 1, т. е. (32(k+1)+1 + 40(k + 1) – 67) : 64.
Действительно,
32(k+1)+1 + 40(k + 1) – 67 = 32k+3 + 40k – 27 = 9×(32k+1 + 40k – 67) – 320k +576 =
= 9×(32k+1 + 40k – 67) – 64×(5k – 9).
Так как каждое слагаемое делится на 64, то и вся сумма делится на 64.
Таким образом, доказана справедливость утверждения (32n+1 + 40n – 67) : 64
для любого натурального n.
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. Докажите, что при каждом натуральном n число 13×(–50)n + 17×40n – 30 делится на 1989.
2. Докажите, что сумма 
равна 
3. Докажите неравенство Бернулли: (1 + a)n > 1 + na, где a > –1, a ¹ 0, n – натуральное число, большее 1.
4. Докажите, что при любом натуральном n
13 + 23 + … + n3 = (1 + 2 + … + n)2.
5. Докажите, что число (1 +
)2012 представляется в виде а + b, где а и b – взаимно простые числа.
6. Докажите, что при любом натуральном n справедливо равенство
7. Докажите методом математической индукции:
а) 1×4 + 2×7 + 3×10 + …+ n(3n+1) = n(n+1)2.
б) (n+1)×(n+2)×…×(n+n)=2n×1×3×5×…×(2n – 1).
в) 
.
г) 
.
д) 2×12 + 3×22 + …+(n+1)n2=
.
е) 
8. Последовательность {an} задана рекуррентным способом: а1=1, а2=1 и аn+2=an+1+
для n ³ 1. Докажите, что an < 3 при всех n.
9. Числа а1, а2, …, an таковы, что 0 £ а1 £ а2 £ 2а1, а2 £ а3 £ 2а2, …, an–1 £ an £ 2an–1. Докажите, что в суммме S = ± a1 ± a2 ± … ± an можно так выбрать знаки, чтобы было 0 £ S £ a1.
10. На плоскости дан набор из n векторов, длина каждого из которых не превосходит единицы. Докажите, что, заменив некоторые векторы из этого набора на противоположные, можно получить набор векторов, сумма которых имеет длину, не превосходящую 
.
11. Последовательность а1, а2, а3, … образована по следующему правилу:
а1 = 1, а2 = а1 + 
, …, аn = an–1 + 
.
Докажите, что а100 > 14.
