Методическая разработка занятия кружка . "Метод математической индукции"

ГБОУ РМЭ «Лицей им. М.В. Ломоносова»

Копылова Ирина Александровна

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

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

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

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

Почему же тогда верны все утверждения ряда? Первое утверждение верно по базе индукции. По переходу индукции мы получаем, что если верно первое утверждение ряда, то верно и второе. Значит, верно и второе утверждение. Еще раз применяем переход: если верно второе утверждение, то верно и третье. Значит, третье утверждение тоже верно. Сделав еще один такой шаг, мы получим, что верно и четвертое утверждение. Затем - пятое, шестое... десятое... сотое... тысячное... миллионное... В общем, верно утверждение ряда со сколь угодно большим номером, то есть любое, то есть каждое - что и требовалось доказать.

Суть доказательства методом математической индукции стоит в следующем. Допустим у нас есть последовательность утверждений A₁, A₂, ... , A_n, A_n+1, ..., где n ∈ N. Все утверждения будут истинными, если:

1) Будет доказана база индукции, т.е. истинность утверждения A₁;

2) Будет доказан переход, т.е. для любого n будет доказано, что если утверждение A_n - верно, то верно и утверждение A_n+1.

Пример1:

Доказать, что если k ∈ N, то число k² - k - четное.

Решение: Решим задачу с помощью метода математической индукции.

1.     Проверим базу индукции - при k = 2, k² - k = 2 - число четное.

2.     Докажем переход. Допустим при некотором k = n, число n² - n - четное.

3.     Докажем, что k = n+1 число (n + 1)²- (n + 1) - тоже четное.

(n + 1) = n² + 2n + 1 - n - 1 = n² + n = n² - n + 2n.

 Число n² - n - четное, согласно предположению и 2n - четное. Сумма четных чисел - четная. Переход доказан.

Потому при любом k ∈ N число k² - k - четное.

Пример2

 Из квадрата 16x16 клеток вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на уголки из трех клеток.

Решение №1:

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

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

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

А от квадрата 8x8 можно точно так же перейти к квадрату 16x16, составив его из четырех частей - получаем ч.т.д (пример разрезания всего квадрата 16x16 на уголки - см. рис. внизу).

Решение №2: (то же самое, но с волшебным словом "индукция")

Докажем по индукции следующее утверждение:

 квадрат (2n)x(2n) с одной вырезанной клеткой можно разрезать на уголки из трех клеток.(На самом деле, здесь спрятан бесконечный ряд утверждений: про квадрат 2x2, 4x4, 8x8, 16x16... 1024x1024 и т.д.)

База: Квадрат 2x2 с одной вырезанной клеткой можно разрезать на уголки. Это верно, т.к. после вырезания клетки от квадрата 2x2 остается один уголок.
Переход: Если квадрат 2nx2n с одной вырезанной клеткой можно разрезать на уголки, то можно разрезать и квадрат (2n+1)x(2n+1).

Действительно, квадрат (2n+1)x(2n+1) составлен из четырех квадратов (2n)x(2n). В одном из них вырезана клетка, а в остальных трех квадратах вырежем по клетке, отрезав уголок, прилежащий к центру исходного квадрата. Тогда каждый из этих четырех квадратов можно будет разрезать на уголки по предположению индукции, значит, можно разрезать и исходный квадрат, ч.т.д.

Пример3

Докажите, что число из 243 единиц делится на 243

Решение:

Докажем по индукции утверждение: число из 3n единиц делится на 3n База: 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 (иногда бывают тождества, которые верны, начиная с числа, большего 1, например, с n=2 или с n=3)
Переход: если тождество верно при каком-то значении n, то верно и при значении n, на единицу большем, то есть при n=n+1.

Задача1.

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

Решение:

База: n=1 - и действительно, 1=1(1+1)/2.
Переход: Пусть тождество верно для какого-то значения  n=k  и  докажем, что оно верно и для значения, на 1 большего, т.е. для n=k+1

Теперь  предположение индукции будет выглядеть, как 1+2+...+k=  ,

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

1+2+...+k+(k+1) =  + k+1  по предположению индукции (т.е. по первому равенству).

 А это равно (k+1) +1) = (k+1) , что и требовалось доказать

Задача 2.

Докажите, что  сумма первых n нечетных чисел равна квадрату их количества.

1+3+...+(2n-1)= n²

Решение:

База: n=2 - действительно, 1+3=2²
Переход: Предположение индукции:  пусть утверждение верно при  n=k , то есть 1+3+...+(2k-1)=k²

 Утверждение, которое надо доказать- верно при n=k+1:

 1+3+...+(2k-1)+(2(k+1)-1) = (k+1)²

 1+3+...+(2k-1)+(2k+1) = (k+1)²

 Его левая часть, по предположению индукции - это k²+2k+1, что, конечно же, равно (k+1)², ч.т.д.

Задача 3.

Докажите, что +8n-9  делится на 16 при любом натуральном n.

Решение:

База: n=1 - действительно,  - делится на 16.
Переход:  если при n=k   +8k - 9  делится на 16, то докажем, что и при n=k+1 число  + 8(k+1) - 9   делится на 16.

+ 8(k+1) - 9   =  +8k +8 - 9   =  +8k  +8- -9=  +8k  +9

 Сумма последних трех слагаемых делится на 16 по предположению, а первое делится на 16 как произведение 8 и четного числа    , ч.т.д.

Упражнения:

 Докажите по индукции следующие формулы:
1. 1²+2²+...+n² =

2. 12+23+...+(n-1)=  

3. 1³+2³+...+n³  =

4. ….=

5.  1+x+x²+...+ xⁿ  =  

Замечание. 

В этом тождестве есть еще переменная x, но индукция ведется по n

6.   …+

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

Задача 4.

Докажите, что >n при любом натуральном n.

Решение:

База: n=1 - действительно, 2¹=2>1.
Переход: Предположим, что при некотором n=k  >k.

Теперь докажем, что >k+1.

Действительно,  = >2по предположению.

Но  2n>n+1 при всех n (очевидно), откуда >n+1, ч.т.д.

Индукция в геометрии.

         Для индукции нужен параметр, по которому ее можно провести, натуральная переменная, значением которой можно занумеровать ряд утверждений.

 Где же ее - переменную - взять в геометрии?
Ответ неожиданно прост: количество фигур или структурная сложность фигуры. Переход тогда производится от меньшего числа фигур к большему или от более простой фигуры к более сложной (хороший пример последнего - удвоение клетчатой доски в примере 2).

Задача 1.

 Плоскость поделена на области несколькими прямыми. Докажите, что области можно раскрасить в два цвета так, чтобы любые две соседние были разных цветов (как принято говорить, "шахматная раскраска").

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

По предположению индукции, полученную картинку  (на ней уже не n+1 прямая, а n) раскрасить можно.

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

Упражнение:

Докажите то же самое, если плоскость поделена не только прямыми, но и окружностями.

Задача 2.

А на сколько областей делят плоскость эти n прямых, если они в общем положении? ("В общем положении" - это когда никакие прямые не параллельны, и никакие три не пересекаются в одной точке.)

Решение:

 Одна прямая поделит плоскость на 2 части, 2 прямых - на 4 части, 3 прямых - (см. рис) на 7 частей, 4 прямых (если не лень их провести) - на 11 частей.

Кажется, что при добавлении  n-й  прямой число частей увеличивается на  n.  То есть ответ будет 1+(1+2+...+n) -  на 1 больше треугольного числа. Это мы угадали. А давайте теперь докажем (часто в задачах на индукцию ответ надо угадывать).

База: Для n=1 уже была проверена. При угадывании ответа заодно проверяется база индукции )
Переход: (проведем его не "от  n  к  n+1 ", а "от  n-1  к  n ").

Пусть  n-1  прямых разбили плоскость на 1+(1+2+...+(n-1))  частей.

 Добавим n- ю прямую: она пересечет все предыдущие и притом в различных точках (потому что они в общем положении!), поэтому она пересечет n областей. Каждая область от этого поделится на две, поэтому число областей увеличится на n  и станет равно 1+(1+2+...+n),  ч.т.д.

Задача 3.

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

Решение: Докажем индукцией по числу сторон многоугольника (это есть "структурная сложность фигуры").

База: n=4. Построить четырехугольник с тремя острыми углами нетрудно. Например, пристроив к основанию равнобедренного треугольника с углами 20, 20, 140, равносторонний треугольник с такой же стороной, получаем четырехугольник с углами 60, 80, 80, 140 (все углы в градусах!).
Переход: (от n сторон к  n+1 стороне)

 Давайте возьмем какой-нибудь тупой угол нашего n-угольника (а их у нас целых n-3) и "отпилим" (как по пунктиру на рис.). Появятся два новых тупых угла (они тупые, так как смежные с ними острые - они лежат в одном треугольнике с исходным тупым углом), т.е. мы получим n+1 угольник.

А три острых угла в нем останутся, ч.т.д.

Разнообразие индукции в природе.

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

Задача 1.

 Число   - целое. Докажите, что      тоже целое при любом натуральном   n

Решение:

Попробуем провести индукцию по N.

Начнем с перехода - докажем, что      целое

Знаем, что    - целое. Умножим его тоже на что-нибудь целое,  так чтобы в произведении просматривалось    - на  ( x ,  например.

Тогда       =      - появилось предыдущее слагаемое, со степенью n-1.

Конечно, если оно целое и      тоже, то нет сомнений, что

     целое.

А  раз уж      целое, то    - предыдущее слагаемое - тем более. Как же это строго записать?

Переход: Если два выражения вида   с  подряд  идущими значениями n целые, то и при следующем значении  n  выражение целое (то есть, обозвав буквой  n значение, мы получаем переход от n-1 и n к n+1). Это мы только что научились доказывать. А какая должна быть база такой индукции?
База:    x и     целые.

Т.е. мы проверяем базу при n=1 и n=2. Первое верно по условию, второе  следует  из равенства        -2, ч.т.д.

Правильность такой индукции вне сомнений:

при n=1 и n=2 доказываемое утверждение (т.е. первые два утверждения ряда) верно по базе.

 Если верно при n=1 и n=2, то, согласно переходу, верно и при n=3. Теперь, раз верно при  n=2 и n=3, то верно и при n=4 . Далее - при n=5, 6 и т.д.

Задача 2.

Докажите, что любое натуральное число можно представить в виде суммы различных степеней 2.

Решение:

Здесь мы используем вторую по распространенности схему индукции: "переход от всех чисел, не больших  n , к  n+1 " или "от всех чисел, меньших n,  к  n".

То есть верность очередного утверждения ряда следует из верности не одного, а всех предыдущих.

Действительно, если верно первое утверждение (т.е. есть представление для 1), то верно и второе (есть представление для 2). Если верны первые 2, то верно и третье (представление для 3). Если же верны первые три утверждения, то из них следует четвертое и т.д.
База: n=1. Ну, единица, сама по себе, уже степень двойки: 1=2⁰.
Переход: Докажем, что если есть представления у всех меньших чисел, то есть и у n.

Пусть т.е. m - показатель максимальной степени 2, не превосходящей   n.   

Если  n=  , то представление найдено.

 Если нет, то вычтем из n число  ,  получим: 

       

И  эту разность мы представим, как сумму степеней двойки, по предположению индукции.

При этом, т.к.         , то m-й степени в этом представлении не будет и, добавив к нему     , мы получим представление n  в виде суммы различных степеней 2, ч.т.д.

Упражнение:

Докажите  неравенство о средних:  среднее арифметическое не меньше среднего геометрического, т.е.      

Подсказка: (приведем только план)
1)  Докажем базу: неравенство при  n=2.
2)  Применяя базу, доказываем переход от  n  к  2n  - таким образом, мы докажем неравенство для  n = 4, 8, 16... и  для всех степеней двойки.
3)  Теперь, вставляя лишнее число, равное какому-то среднему остальных, мы придумываем переход от n к n-1. Поскольку для каждого натурального числа есть большая его степень двойки, то мы доказали неравенство при всех значениях n.