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

Кружок 9-11 классов

Математическая индукция

Часто требуется доказать утверждение типа: „Для каждого натурального n верно, что ...” Такое утверждение можно рассматривать как цепочку утверждений „Для n = 1 верно, что ...”, „Для n = 2 верно, что ...”, и т.д.

Метод математической индукции состоит в том, чтобы:

1. Доказать первое из этих утверждений (называемое базой индукции).
2. Затем доказать переход индукции: „Если верно утверждение с номером k, то верно утверждение с номером (k + 1)”.

Если верна база индукции и верен шаг индукции, то все утверждения верны.

Пример. Докажите, что для всякого натурального n выполнено равенство: \(1+2+3+\ldots+n = \frac {n(n + 1)}{2}\).

Доказательство.
База. При n = 1 имеем \(1 = \frac{1\cdot2}{2}\). Очевидно, что это верно.
Переход. Пусть верно утверждение с номером n, докажем его для n + 1. По предположению индукции верно равенство: \(1 + 2 + ... + n = \frac {n(n + 1)}{2}\). Имеем: \(1 + 2 + \ldots + n + (n + 1) = \frac{n(n + 1)}{2}+(n + 1)= \frac{n(n +1) + 2(n + 1)}{2}=\frac{(n + 1)(n + 2)}{2}\). Переход доказан.

1.

Докажите тождества:

а)

1 + 3 + 5 + ... + (2n − 1) = n².

б)

\(1^3+2^3+ ... +n^3 = \frac{1}{4}n^2(n + 1)^2\).

2.

Несколько прямых делят плоскость на части. Докажите, что эти части можно раскрасить в 2 цвета так, что граничащие части будут иметь разный цвет.

3.

Ханойская башня. Есть три жерди — две пустые, а на первой пирамидка из дисков. В пирамидке на каждом диске лежит диск меньшего размера. Разрешается перекладывать по одному диску с одной жерди на другую при условии, что диск кладут на больший диск. Можно ли перетащить все диски с первой жерди на третью, если дисков: а) 2; б) 3; в) 5; г) n?

4.

N прямых общего положения (т.е. никакие три не пересекаются в одной точке) разбивают плоскость на части, докажите что хотя бы одна из частей — треугольник.

5.

Известно, что \(x + \frac{1}{x}\) — целое число. Докажите, что \(x^n + \frac{1}{x^n}\) также целое при любом целом n.

6.

Докажите, что сумма углов выпуклого n-угольника равна 180°(n − 2).

7.

Докажите, что 4ⁿ + 15n − 1 при любом натуральном n кратно 9.

8.

На плоскости нарисовано несколько окружностей, каждая пересекается с каждой. Доказать, что эту картинку можно обвести «одним росчерком», то есть не проходя по одной дуге два раза и не отрывая карандаша от бумаги, и при этом вернуться в начальную точку.