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

Метод математической индукции - не просто распространенный метод решения олимпиадных задач, но и способ доказательства многих утверждений в математической науке. (Не случайно эта лекция такая длинная!) Поэтому знать этот метод нужно не только математику-олимпиаднику, но и каждому, кто собирается в дальнейшем изучать высшую математику или теорию алгоритмов. Что же такое индукция?

Часто индукцию сравнивают с падением ряда доминошек: мы толкаем первую доминошку - она падает и задевает вторую. Вторая доминошка от этого тоже падает и задевает третью. Теперь падает третья доминошка, задевает четвертую... - и в итоге падает весь ряд. А происходит это по двум причинам:
1.) Мы толкаем первую доминошку.

2.) Любая доминошка, падая, задевает следующую.

Доказательство по индукции протекает аналогичным образом. У нас есть ряд утверждений (обычно - бесконечно длинный), которые надо доказать. И для этого достаточно доказать всего два утверждения:

1.) База индукции: первое утверждение ряда верно.

2.) Переход индукции: если верно какое-то утверждение ряда (неважно, какое именно ), то верно и следующее за ним утверждение ряда. (эти два пункта аналогичны пунктам про падающие доминошки!)

Почему же тогда верны все утверждения ряда? Первое утверждение верно по базе индукции. По переходу индукции мы получаем, что если верно первое утверждение ряда, то верно и второе. Значит, верно и второе утверждение. Еще раз применяем переход: если верно второе утверждение, то верно и третье. Значит, третье утверждение тоже верно. Сделав еще один такой шаг, мы получим, что вернои четвертое утверждение. Затем - пятое, шестое... десятое... сотое... тысячное... миллионное... В общем, верно утверждение ряда со сколь угодно большим номером, то есть любое, то есть каждое - что и требовалось доказать.
Такой ряд утверждений, где у каждого утверждения есть свой порядковый номер (" первое", " второе" и т.п.) по-научному называется " ряд утверждений, занумерованных натуральными числами". И факт наличия в задаче такого ряда следует понимать весьма творчески. Часто имеется одно утверждение (У), но в нем есть какой-то параметр (например, n), являющийся натуральным числом. Тогда первое утверждение ряда (У₁) - это утверждение У при n=1. Второе утверждение ряда (У₂) - это утверждение У при n=2... сотое (У₁₀₀) - это утверждение У при n=100 и т.д. Часто утверждение У - это тождество с одной натуральной переменной (иногда и с несколькими - но об этом ниже). Иногда в задаче просят доказать только одно конкретное утверждение ряда (например, У₅, У₇ или У₁₀) - но это нельзя сделать проще, чем доказать весь ряд по индукции (см. примеры ниже).

Пример. Из квадрата 16x16 клеток вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на уголки из трех клеток.
Решение № 1. Что делать, если не хочется рассматривать кучу разных случаев вырезания клетки из квадрата 16x16 (как ни сокращай, но 36 принципиально разных случаев там есть)? Давайте посмотрим на квадраты поменьше (но тоже со стороной, равной степени двойки): 8x8, 4x4, 2x2. Для 2x2 доказывать нечего: вырезали любую клетку, и остался один уголок. А вот теперь посмотрим на квадрат 4x4 - он составлен из 4-х квадратов 2x2 (см. рис.). В один из них попадет вырезанная клетка (черная на рис.) - и он разрежется на уголки (т.е., как сказано выше, там будет ровно 1 уголок). Что же делать с тремя другими? (это и есть самый сложный для момент в задаче!) А давайте возьмем в этих трех квадратах уголок, прилежащий к центру большого квадрата - и отрежем его (серые клетки на рис.). Тогда у нас останется три квадратика 2x2 с вырезанной клеткой - а их мы уже умеем разрезать на уголки.

Теперь перейдем от 4x4 к 8x8: квадратик 8x8 составен из четырех квадратиков 4x4. В одном из них есть вырезанная клетка, а в остальных трех мы вырежем по клетке, отрезав прилежащий к центру уголок (аналогично предыдущему). Теперь образуется 4 квадратика 4x4, в каждом из которых вырезана клетка. Каждый из них мы умеем разрезать на уголки - значит, разрежем и весь квадрат 8x8. А от квадрата 8x8 можно точно так же перейти к квадрату 16x16, составив его из четырех частей - получаем ч.т.д (пример разрезания всего квадрата 16x16 на уголки - см. рис. внизу).

Решение №2. (то же самое, но с волшебным словом " индукция") Докажем по индукции следующее утверждение: квадрат 2ⁿx2ⁿ с одной вырезанной клеткой можно разрезать на уголки из трех клеток.(На самом деле, здесь спрятан бесконечный ряд утверждений: про квадрат 2x2, 4x4, 8x8, 16x16... 1024x1024 и т.д.)
База: Квадрат 2x2 с одной вырезанной клеткой можно разрезать на уголки. Это верно, т.к. после вырезания клетки от квадрата 2x2 остается один уголок.
Переход: Если квадрат 2ⁿx2ⁿ с одной вырезанной клеткой можно разрезать на уголки, то можно разрезать и квадрат 2ⁿ⁺¹x2ⁿ⁺¹. Действительно, квадрат 2ⁿ⁺¹x2ⁿ⁺¹ составлен из четырех квадратов 2ⁿx2ⁿ. В одном из них вырезана клетка, а в остальных трех квадратах вырежем по клетке, отрезав уголок, прилежащий к центру исходного квадрата. Тогда каждый из этих четырех квадратов можно будет разрезать на уголки по предположению индукции, значит, можно разрезать и исходный квадрат, ч.т.д.

Замечание: предположением индукции называется предположение о верности очередного утверждения ряда, из верности которого мы в переходе индукции доказываем верность следующего утверждения ряда.

(!) Когда задача решается по индукции, то решение записывается в стиле, похожем на решение №2. Но придумывается оно часто в стиле решения №1 - так бывает удобнее, особенно для начинающих; -)
А настоящее овладение методом- это умение придумывать решение сразу таким, как оно будет записано; -)

Пример. Докажите, что число из 243 единиц делится на 243.
Решение №1: Давайте опять попробуем что-нибудь попроще. Например, 111 делится на 3, а число 111111111 - на 9. Это, конечно, правда, по общеизвестным признакам делимости на 3 и на 9 (на 3 и на 9 делится сумма цифр этих чисел). Но дальше признаки делимости заканчиваются: (Что же делать? Давайте по-другому докажем, что 111111111 делится на 9 - так, чтобы можно было из этого сделать переход в общем виде. Конечно, надо пользоваться тем, что в общем виде будет предположением индукции: 111 делится на 3. А давайте 111111111 на него поделим - в частном будет 1001001. Это частное, конечно, делится на 3 (по тому же признаку). А произведение двух чисел, делящихся на 3, делится на 9.
Идем дальше: почему число из 27 единиц делится на 27? Поделим его на 111111111 и получим в частном 10¹⁸+10⁹+1. Это частное опять делится на 3 (его сумма цифр 3), а делитель, как мы уже знаем, на 9. Поэтому число из 27 единиц делится на 9*3=27. Само это число будет делителем числа из 81 единицы, и в частном получается уже 10⁵⁴+10²⁷+1 - все равно оно на 3 делится, по тем же причинам. А число из 81 единицы поделится тогда на 27*3=81, что и следовало ожидать. Еще один такой же переход - и мы получим, что число из 243 единиц делится на 243, ч.т.д.
(!) Важная мысль: здесь, переходя к предыдущим шагам, мы уменьшаем уже не один, а оба параметра: число, которое должно делится, и число, на которое оно должно делится.

Решение №2: (опять то же самое, но сторого индуктивно записанное) Докажем по индукции утверждение: число из 3ⁿ единиц делится на 3ⁿ (т.е. бесконечный ряд утверждений при разных натуральных n).

База: 111 делится на 3 (n=1). Святая правда. В частном 37 получается.
Переход: Заметим, что число из 3ⁿ⁺¹ единиц делится на число из 3ⁿ единиц, и в частном будет 10^2*3n+10³ⁿ+1 (т.е. число из трех единиц и кучи нулей). Делитель, по предположению индукции, делится на 3ⁿ, а частное - на 3 (т.к. его сумма цифр 3). Значит, число из 3ⁿ⁺¹ единиц делится на 3ⁿ*3=3ⁿ⁺¹, ч.т.д.
Замечание: Можно доказать, опять же по индукции, что число из 3ⁿ единиц содержит 3 в степени ровно n. При n=1 это верно (база), а дальше заметим, что частное от деления числа из 3ⁿ⁺¹ единиц на число из 3ⁿ единиц делится только на 3, но не на 9, т.к. его сумма цифр равна 3 (переход).

Мы заметили некоторую закономерность в значениях изучаемой последовательности. Проверяем эту закономерность для n=1. Предполагаем, что формула справедлива при некотором n и доказываем, что она справедлива для n=n+1. Подставляем в формулу n+1 и получаем формулу, которой соответствует (n+1) – ый член. Затем получаем (n+1) – ый член, исходя из общего принципа построения последовательности. Получим формулу для n+1. Если эти формулы совпадают, то закономерность считается доказанной.

Пример:

S , при n=1 эта формула справедлива: Пусть она справедлива при некотором n. Если она справедлива для n+1, то должно быть S .

Получим эту формулу из общих соображений.

S_n+1 = S_n + n +1 = + n+1 = (n+1) ( +1) =

Что и требовалось доказать.

Пример. Докажите, что 1+2+...+N=N(N+1)/2 (такие числа называются " треугольными": 1, 3, 6, 10, 15, 21, 28...).

Решение: Докажем по индукции (обычно говорят " докажем индукцией по N", т.е. по переменной, значением которой нумеруются утверждения в ряду).
База: N=1 - и действительно, 1=1(1+1)/2.

Переход: Пусть тождество верно для какого-то значения N, которое мы теперь тоже обозначим за N. Надо доказать, что оно верно и для значения, на 1 большего, т.е. (в новом смысле буквы N) для N+1. Теперь предположение индукции будет выглядеть, как 1+2+...+N=N(N+1)/2, а то, что надо доказать - как результат подстановки сюда N+1 вместо N, т.е. 1+2+...+N+(N+1)=(N+1)(N+2)/2.

Техническая часть - из одного равенства вывести другое - трудностей не представляет: 1+2+...+N+(N+1) = N(N+1)/2+(N+1) - по предположению индукции (т.е. по первому равенству). А это равно (N+1)(N/2+1) = (N+1)(N+2)/2, ч.т.д.

Пример. Докажите, что 1+3+...+(2N-1)=N² - сумма первых N нечетных чисел равна N².
Решение: Докажем индукцией по N, но теперь эту идейную подтасовку будет опускать.
База: N=1 - действительно, 1=1².

Переход: Предположение индукции: 1+3+...+(2N-1)=N² - так и пишут в индуктивных доказательствах, скрывая ту подтасовку, которая была продемонстрирована в решении предыдущей задаче (и сбивая с толку тех, кто плохо понимает метод индукции!). Утверждение, которое надо доказать: 1+3+...+(2N-1)+(2*(N+1)-1) = (N+1)² - т.е. 1+3+...+(2N-1)+(2N+1) = (N+1)². Его левая часть, по предположению индукции - это N²+2N+1, что, конечно же, равно (N+1)², ч.т.д.

Пример. Докажите, что 2^N> N при любом натуральном N.
Решение: Докажем индукцией по N (и тут, и далее в переходе применяется все та же идейная подтасовка!).

База: N=1 - действительно, 2¹=2> 1.

Переход: Предположим, что при некотором N 2^N> N. Теперь докажем, что 2^N+1> N+1. Действительно, 2^N+1=2*2^N> 2N по предположению. А 2N> =N+1 при всех N (очевидно), откуда 2^N+1> N+1, ч.т.д.

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

Пример. Докажите, что 3^2N+2+8N-9 делится на 16 при любом натуральном N.
Решение: Докажем индукцией по N.

База: N=1 - действительно, 3^2*1+2+8*1-9=80 - делится на 16.

Переход: Уже известная махинация сводит доказательство перехода к следующему утверждению: если 3^2N+2+8N-9 делится на 16, то 3^2(N+1)+2+8(N+1)-9 делится на 16. Последнее число равно 3^2N+4+8N+8-9 = 9*3^2N+2+8N+8-9 = 8*3^2N+2+3^2N+2+8N+8-9 = 8*(3^2N+2+1)+3^2N+2+8N-9 Сумма последних трех слагаемых делится на 16 по предположению, а первое - как произведение 8 и четного числа 3^2N+2+1, ч.т.д.