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

Известный литературный герой Шерлок Холмс, раскрывая преступления, в качестве метода своей работы использовал дедукцию. Дедуктивные рассуждения – это то, что в математике называют логическими рассуждениями, или переход от общего к частному. И в математической науке дедукция является самым распространенным методом исследования. Правила логических рассуждений были сформулированы два с половиной тысячелетия назад древнегреческим учёным Аристотелем (силлогизмы).

Но есть и еще один способ рассуждений – от частного к общему. Такой метод носит название индукция. Индукция (induction– по-латыни наведение). То есть один или несколько частных случаев «наводят» на общее утверждение, общий вывод делается на основании частных наблюдений. Однако, индуктивный метод имеет весьма существенный недостаток: на основании частных примеров может быть сделан неверный вывод. Гипотезы, возникающие при частных наблюдениях, не всегда являются правильными. Рассмотрим пример, принадлежащий Эйлеру.

Будем вычислять значение трехчлена n² +n+41 при некоторых первых значениях n:

n	1	2	3	4	5	6	7	8
	43	47	53	61	71	83	97	113

Заметим, что получаемые в результате вычислений числа являются простыми. И непосредственно можно убедиться, что для каждого n от 1 до 39 значение многочлена является простым числом. Однако при n=40 получаем число 1681=41², которое не является простым. Таким образом, гипотеза, которая здесь могла возникнуть, то есть гипотеза о том, что при каждом n число n²+n+41 является простым, оказывается неверной.

Таким образом, утверждение может быть справедливым в целом ряде частных случаев и в то же время несправедливым вообще. Поэтому в математике такой метод не используют, но применяют особый метод рассуждений, который называется методом математической индукции (полной индукции, совершенной индукции). Этот метод подразумевает полный перебор всех частных случаев. Однако прямой перебор не всегда возможен (учитывая, что множество чисел, для которых надо проверить то или иное утверждение, бесконечно). Поэтому для доказательства используют следующую схему:

1 шаг. Проверяем истинность утверждения P(п) для п = 1.

2 шаг. Предполагаем, что P(п) истинно для п = к (к - произвольное натуральное число).

3 шаг. Доказываем, что Р(п) истинно, для п = к + 1.

htitybt

Заменим в левой части равенства первые к слагаемых их суммой из 2-го шага:

решение

В числителе левой части раскроем скобки:

решение

Способом группировки разложим числитель левой части на множители:

решение

Равенство верно.

Задание 2.

(Задача из книги А. Шеня «Математическая индукция», Москва, издательство МЦНМО, 2007)

Игрушка «Ханойские башни» имеет три стержня. На одном находится пирамидка из нескольких колец (уменьшающихся снизу вверх). Эту пирамидку нужно переложить на другой стержень, соблюдая правила игры: нельзя переносить сразу несколько колец и нельзя класть большее кольцо поверх меньшего. Например, пирамидку из двух колец можно переложить так: положить меньшее кольцо на второй стержень, затем большее на третий, а затем меньшее поверх большего. Доказать, что возможно переместить на другой стержень пирамидку из любого числа колец, соблюдая правила игры.

Задание 3.

задача