Индукция

Ноя 16 2014

Лекция  «Индукция.»

Метод математической индукции — не просто распространенный метод решения олимпиадных задач, но и способ доказательства многих утверждений в математической науке. (Не случайно эта лекция такая длинная!) Поэтому знать этот метод нужно не только математику-олимпиаднику, но и каждому, кто собирается в дальнейшем изучать высшую математику или теорию алгоритмов. Что же такое индукция?Часто индукцию сравнивают с падением ряда доминошек: мы толкаем первую доминошку — она падает и задевает вторую. Вторая доминошка от этого тоже падает и задевает третью. Теперь падает третья доминошка, задевает четвертую… — и в итоге падает весь ряд. А происходит это по двум причинам:
1.) Мы толкаем первую доминошку.
2.) Любая доминошка, падая, задевает следующую.
Доказательство по индукции протекает аналогичным образом. У нас есть ряд утверждений (обычно — бесконечно длинный), которые надо доказать. И для этого достаточно доказать всего два утверждения:
1.) База индукции: первое утверждение ряда верно.
2.) Переход индукции: если верно какое-то утверждение ряда (неважно, какое именно), то верно и следующее за ним утверждение ряда. (эти два пункта аналогичны пунктам про падающие доминошки!)
Почему же тогда верны все утверждения ряда? Первое утверждение верно по базе индукции. По переходу индукции мы получаем, что если верно первое утверждение ряда, то верно и второе. Значит, верно и второе утверждение. Еще раз применяем переход: если верно второе утверждение, то верно и третье. Значит, третье утверждение тоже верно. Сделав еще один такой шаг, мы получим, что вернои четвертое утверждение. Затем — пятое, шестое… десятое… сотое… тысячное… миллионное… В общем, верно утверждение ряда со сколь угодно большим номером, то есть любое, то есть каждое — что и требовалось доказать.
Такой ряд утверждений, где у каждого утверждения есть свой порядковый номер («первое», «второе» и т.п.) по-научному называется «ряд утверждений, занумерованных натуральными числами». И факт наличия в задаче такого ряда следует понимать весьма творчески. Часто имеется одно утверждение (У), но в нем есть какой-то параметр (например, n), являющийся натуральным числом. Тогда первое утверждение ряда (У1) — это утверждение У при n=1. Второе утверждение ряда (У2) — это утверждение У при n=2… сотое (У100) — это утверждение У при n=100 и т.д. Часто утверждение У — это тождество с одной натуральной переменной (иногда и с несколькими — но об этом ниже). Иногда в задаче просят доказать только одно конкретное утверждение ряда (например, У5, У7 или У10) — но это нельзя сделать проще, чем доказать весь ряд по индукции (см. примеры ниже).

Задача 1. Докажите, что число из 243 единиц делится на 243.
Решение №1: Давайте опять попробуем что-нибудь попроще. Например, 111 делится на 3, а число 111111111 — на 9. Это, конечно, правда, по общеизвестным признакам делимости на 3 и на 9 (на 3 и на 9 делится сумма цифр этих чисел). Но дальше признаки делимости заканчиваются :(
Что же делать? Давайте по-другому докажем, что 111111111 делится на 9 — так, чтобы можно было из этого сделать переход в общем виде. Конечно, надо пользоваться тем, что в общем виде будет предположением индукции: 111 делится на 3. А давайте 111111111 на него поделим — в частном будет 1001001. Это частное, конечно, делится на 3 (по тому же признаку). А произведение двух чисел, делящихся на 3, делится на 9.
Идем дальше: почему число из 27 единиц делится на 27? Поделим его на 111111111 и получим в частном 1018+109+1. Это частное опять делится на 3 (его сумма цифр 3), а делитель, как мы уже знаем, на 9. Поэтому число из 27 единиц делится на 9*3=27. Само это число будет делителем числа из 81 единицы, и в частном получается уже 1054+1027+1 — все равно оно на 3 делится, по тем же причинам. А число из 81 единицы поделится тогда на 27*3=81, что и следовало ожидать. Еще один такой же переход — и мы получим, что число из 243 единиц делится на 243, ч.т.д.
(!) Важная мысль: здесь, переходя к предыдущим шагам, мы уменьшаем уже не один, а оба параметра: число, которое должно делится, и число, на которое оно должно делится.
Решение №2: (опять то же самое, но сторого индуктивно записанное) Докажем по индукции утверждение: число из 3n единиц делится на 3n (т.е. бесконечный ряд утверждений при разных натуральных n).
База: 111 делится на 3 (n=1). Святая правда. В частном 37 получается.
Переход: Заметим, что число из 3n+1 единиц делится на число из 3n единиц, и в частном будет 102*3n+103n+1 (т.е. число из трех единиц и кучи нулей). Делитель, по предположению индукции, делится на 3n, а частное — на 3 (т.к. его сумма цифр 3). Значит, число из 3n+1 единиц делится на 3n*3=3n+1, ч.т.д.
Замечание: Можно доказать, опять же по индукции, что число из 3n единиц содержит 3 в степени ровно n. При n=1 это верно (база), а дальше заметим, что частное от деления числа из 3n+1 единиц на число из 3n единиц делится только на 3, но не на 9, т.к. его сумма цифр равна 3 (переход).

Самый распространенный случай применения индукции — доказательство алгебраических формул, а именно — тождеств с натуральной переменной. Как показывает опыт, дети-школьники плохо воспринимают понятие тождества. Специально для них объясняю: «тождество — это такое уравнение, решениемкоторого будет любое число» (если речь тождество с натуральной переменной — то любое натуральное число). Или любой набор чисел, если в тождестве несколько переменных.
Ограничимся пока тождествами с одной натуральной переменной (обозначим ее пока буквой N). Такое тождество можно рассматривать, как ряд утверждений: первое утверждение — «тождество верно при N=1″, второе — «тождество верно при N=2″… десятое — «тождество верно при N=10″ и т.д. И такой ряд утверждений можно (а часто и нужно!) доказывать по индукции. То есть, доказать нужно следующее:
База: тождество верно при N=1 (иногда бывают тождества, которые верны, начиная с числа, большего 1!!!)
Переход: если тождество верно при каком-то значении N, то верно и при значении N, на единицу большем.
Обычно говорят: «если тождество верно для N, то оно верно и для N+1″. За этим кроется такая подтасовка: исходно буква N обозначает переменную, а доказывая переход, мы обозначаем той же буквой конкретное значение этой переменной (то, что тремя строчками выше называется «каким-то значением N»). Тогда условие индукционного перехода записывается точно так же, как и тождество, которое надо доказать. А утверждение, которое нужно вывести из этого условия, есть результат подстановки в это тождество N+1 вместо N. Поэтому обычно говорят «подставим вместо N N+1″. Рассмотрим подробнее на примере:

Задача 2. Докажите, что 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, ч.т.д.

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

Упражнение: Докажите по индукции следующие формулы:
12+22+…+N2=N(N+1)(2N+1)/6; 1*2+2*3+…+(N-1)*N=(N-1)N(N+1)/3 (тут база N=2, а не N=1!)
13+23+…+N3=(N(N+1)/2)2; 1/(1*2)+1/(2*3)+…+1/(N-1)N=(N-1)/N
1+X+X2+…+XN=(XN+1-1)/(X-1) — в этом тождестве есть еще буква X, но индукция ведется по N(!)
(1-1/4)(1-1/9)…(1-1/N2)=(N+1)/2N

Типичные тождества, доказываемые по индукции — сворачивание сумм или произведений, т.е. тождества вида F1+F2+…+FN=SN или F1*F2*…*FN=PN (именно такие и бывали в наших примерах и упражнениях). В этих случаях индукционный переход состоит в выведении из предположения индукции (а оно формулируется так же, как исходное тождество!) равенства F1+F2+…+FN+FN+1=SN+1 или F1*F2*…*FN*FN+1=PN+1. Технический рецепт тут такой: пользуясь предположением, получаем F1+F2+…+FN+FN+1=SN+FN+1 или F1*F2*…*FN*FN+1=PN*FN+1. А далее остается проверить тождество SN+FN+1=SN+1 или PN*FN+1=PN+1, что обычно проблемы не представляет. Иногда лучше перенести в другую часть и доказывать, что FN+1=SN+1-SN или FN+1=PN+1/PN соответственно. Вообще (см. также задачи 5 и 6), в утверждении, которое надо доказать в переходе, всегда надо выделить часть формулы, с которой можно разобраться, применяя предположение (!).

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

Задача 4. Докажите, что 2N>N при любом натуральном N.
Решение: Докажем индукцией по N (и тут, и далее в переходе применяется все та же идейная подтасовка!).
База: N=1 — действительно, 21=2>1.
Переход: Предположим, что при некотором N 2N>N. Теперь докажем, что 2N+1>N+1. Действительно, 2N+1=2*2N>2N по предположению. А 2N>=N+1 при всех N (очевидно), откуда 2N+1>N+1, ч.т.д.

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

Задача 5. Докажите, что 32N+2+8N-9 делится на 16 при любом натуральном N.
Решение: Докажем индукцией по N.
База: N=1 — действительно, 32*1+2+8*1-9=80 — делится на 16.
Переход: Уже известная махинация сводит доказательство перехода к следующему утверждению: если 32N+2+8N-9 делится на 16, то 32(N+1)+2+8(N+1)-9 делится на 16. Последнее число равно 32N+4+8N+8-9 = 9*32N+2+8N+8-9 = 8*32N+2+32N+2+8N+8-9 = 8*(32N+2+1)+32N+2+8N-9 Сумма последних трех слагаемых делится на 16 по предположению, а первое — как произведение 8 и четного числа 32N+2+1, ч.т.д.

Метки:

Нет ответов пока

Вы должны ввойти чтобы оставить комментарий.