МАЛЫЙ МЕХМАТ МГУ

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

Пусть мы имеем бесконечную последовательность утверждений P₁, P₂, ..., P_n, ..., занумерованных натуральными числами, причём:
— утверждение P₁ истинно;
— если некоторое утверждение P_k истинно, то следующее утверждение P_k+1 тоже истинно.

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

Другими словами принцип математической индукции можно сформулировать так: если в очереди первой стоит женщина, и за каждой женщиной стоит женщина, то все в очереди – женщины.

Способ рассуждений, основанный на принципе математической индукции называется методом математической индукции. Для решения задач методом математической индукции необходимо:
1) сформулировать утверждение задачи в виде последовательности утверждений P₁, P₂, ..., P_n, ...
2) доказать, что утверждение P₁ истинно (этот этап называется базой индукции); 3) доказать, что если утверждение P_n истинно при некотором n = k, то оно истинно и при n = k + 1 (этот этап называется шагом индукции).

Для примера докажем по индукции следующее равенство (которое, конечно, допускает и другие доказательства):
1 + 2 + 3 + ... + n = n(n + 1)/2.

База. При n = 1 равенство превращается в тождество 1 = 1·(1 + 1)/2. Шаг. Пусть равенство выполнено при n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2. Прибавим к обеим частям этого равенства k + 1. В левой части мы получим сумму 1 + 2+ 3 + ... + k + (k + 1), а в правой - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/2. Итак, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2, а это и есть требуемое равенство при n = k + 1.

Во всех задачах n означает произвольное натуральное число.

1.	Докажите следующие равенства: а) 1²+2²+3²+...+n²=n(n+1)(2n+1)/6; б) 1³+2³+3³+...+n³=n²(n+1)²/4.
2.	Из доски 1024×1024 вырезали а) кусок 512×512 из угла; б) одну угловую клетку; в) одну произвольную клетку. Докажите, что оставшуюся часть доски можно разрезать на «уголки» из трёх клеток.
3.	Докажите, что число, десятичная запись которого состоит из 243 единиц, делится на 243.
4.	Докажите, что число 4ⁿ + 15n – 1 делится на 9.
5.	Докажите, что для любого числа x≥-1 справедливо неравенство Бернулли: (1+x)ⁿ≥1 + nx.
6.	Число x + ¹/_x целое. Докажите, что число xⁿ + 1/xⁿ тоже целое.
7.	Найдите ошибку в следующем «доказательстве» того, что все лошади одной масти. Будем доказывать индукцией по n следующее утверждение: «В любом табуне из n лошадей, все они одной масти». База (n = 1) очевидна: в этом случае все лошади - это одна лошадь, она очевидно одной масти. Шаг: пусть в любом табуне из k лошадей все лошади имеют одну масть. Рассмотрим табун из k + 1 лошади. Выберем в нём двух лошадей a и b и рассмотрим оставшиеся k – 1 лошадь. Составим табун из этих оставшихся лошадей, добавив к ним a. В нём k лошадей, поэтому, по предположению индукции, все они одной масти. Значит, лошадь a имеет ту же масть, что и оставшиеся лошади. Аналогично доказывается, что ту же масть имеет лошадь b. Значит, все k + 1 лошадь имеют одинаковую масть. Утверждение доказано.
8.	На бесконечном клетчатом листе бумаги 100 клеток закрашены в чёрный цвет, а все остальные — в белый. За один ход разрешается перекрашивать в противоположный цвет любые четыре клетки, образующие квадрат 2×2. Докажите, что за несколько ходов можно добиться того, что все клетки окажутся белыми тогда и только тогда, когда любая горизонталь и любая вертикаль содержит чётное число чёрных клеток.