Таблицы Брадиса

База индукции проверяется прямым вычислением.

База индукции проверяется прямым вычислением.

Элементы математики в задачах - Г. А. Мерзон

= 17• 25п+3 + 15(25п+3 + 5п • 3п+2).

Первое слагаемое, очевидно, делится на 17. А второе слагаемое де­лится на 17 по предположению индукции.

б)  В этой задаче на первый взгляд непонятно, по какой перемен­ной мы должны вести индукцию: по п или по т? Изложим доказа­тельство, использующее индукцию по т.

База индукции. п21-1 +1 = п +1 делится на п + 1.

Шаг индукции. Предположим, что формула верна для некоторо­го т. Докажем тогда, что она будет верна также, если мы везде вместо т подставим т + 1 :

п2(т+1)-1 + 1 = п2 • п2т-1 +1 = п2 • ((п2т-1 + 1) - 1) + 1 =

= п2 • (п2т-1 + 1) + 1 - п2 = п2 • (п2т-1 +1) + (1 - п)(1 + п).

Полученное произведение делится на п + 1, так как первое слагаемое делится на п + 1 по предположению индукции.

Задача 10 (неравенство Бернулли). Докажите, что если а > —1, то

(1 + а)п ^ 1 + па.

Решение. База индукции. При п = 1 имеем: 1 + а ^ 1 + а — верно.

Шаг индукции. Пусть неравенство Бернулли выполнено для неко­торого п. Докажем тогда, что оно выполняется и для п + 1: (1 + а)п+1 = = (1 + а)(1 + а)п = (1 + а)п + а(1 + а)п. По предположению индукции имеем (1 + а)п ^ 1 + па. Кроме того, а(1 + а)п ^ а, так как а > — 1 (аккуратно докажите это!). Отсюда получаем:

(1 + а)п+1 ^ 1 + па + а = 1 + а(п + 1).

Ш Это неравенство демонстрирует, что показательная функция рас­тет быстрее линейной. Хотя эта оценка довольно грубая, она является мощным средством доказательства неравенств.

Задача 11. Докажите, что:

а) 2п > п; б) 2п > п2 при п > 4; в) п! > 2п при п > 3; г*) существует такое к, что 2п > п2004 при всех п > к.

Решение. База индукции проверяется прямым вычислением. Дока­жем шаг индукции.

а)  2п > п, 2п > 1, значит, 2п+1 = 2п + 2п > п + 1.

б)  2п > п2, 2п > 2п + 1 ^ 2п ■ 2 > п2 + 2п +1 ^ 2п+1 > (п +1)2.