Индукция есть метод получения общего утверждения из частных наблюдений. В случае, когда математическое утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта. Например, утверждение: «Каждое двузначное чётное число является суммой двух простых чисел,» – следует из серии равенств, которые вполне реально установить:
10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.
Метод доказательства, при котором проверяется утверждение для конечного числа случаев, исчерпывающих все возможности, называют полной индукцией. Этот метод применим сравнительно редко, поскольку математические утверждения касаются, как правило, не конечных, а бесконечных множеств объектов. Например, доказанное выше полной индукцией утверждение о четных двузначных числах является лишь частным случаем теоремы: «Любое четное число является суммой двух простых чисел». Эта теорема до сих пор ни доказана, ни опровергнута.
Математическая индукция – метод доказательства некоторого утверждения для любого натурального n основанный на принципе математической индукции: «Если утверждение верно для n=1 и из справедливости его для n=k вытекает справедливость этого утверждения для n=k+1, то оно верно для всех n». Способ доказательства методом математической индукции заключается в следующем:
1) база индукции: доказывают или непосредственно проверяют справедливость утверждения для n=1 (иногда n=0 или n=n 0);
2) индукционный шаг (переход): предполагают справедливость утверждения для некоторого натурального n=k и, исходя из этого предположения, доказывают справедливость утверждения для n=k+1.
Задачи с решениями
1. Доказать, что при любом натуральном n число 3 2n+1 +2 n+2 делится на 7.
Обозначим А(n)=3 2n+1 +2 n+2 .
База индукции. Если n=1, то А(1)=3 3 +2 3 =35 и, очевидно, делится на 7.
Предположение индукции. Пусть А(k) делится на 7.
Индукционный переход. Докажем, что А(k+1) делится на 7, то есть справедливость утверждения задачи при n=k.
А(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 ·3 2 +2 k+2 ·2 1 =3 2k+1 ·9+2 k+2 ·2=
3 2k+1 ·9+2 k+2 ·(9–7)=(3 2k+1 +2 k+2)·9–7·2 k+2 =9·А(k)–7·2 k+2 .
Последнее число делится на 7, так как представляет собой разность двух целых чисел, делящихся на 7. Следовательно, 3 2n+1 +2 n+2 делится на 7 при любом натуральном n.
2. Доказать, что при любом натуральном n число 2 3 n +1 делится на 3 n+1 и не делится на 3 n+2 .
Введём обозначение: а i =2 3 i +1.
При n=1 имеем, а 1 =2 3 +1=9. Итак, а 1 делится на 3 2 и не делится на 3 3 .
Пусть при n=k число а k делится на 3 k+1 и не делится на 3 k+2 , то есть а k =2 3 k +1=3 k+1 ·m, где m не делится на 3. Тогда
а k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k ·2 –2 3 k +1)=3 k+1 ·m·((2 3 k +1) 2 –3·2 3 k)=3 k+1 ·m·((3 k+1 ·m) 2 –3·2 3 k)=
3 k+2 ·m·(3 2k+1 ·m 2 –2 3 k).
Очевидно, что а k+1 делится на 3 k+2 и не делится на 3 k+3 .
Следовательно, утверждение доказано для любого натурального n.
3. Известно, что х+1/x – целое число. Доказать, что х n +1/х n – так же целое число при любом целом n.
Введём обозначение: а i =х i +1/х i и сразу отметим, что а i =а –i , поэтому дальше будем вести речь о натуральных индексах.
Заметим: а 1 – целое число по условию; а 2 – целое, так как а 2 =(а 1) 2 –2; а 0 =2.
Предположим, что а k целое при любом натуральном k не превосходящем n. Тогда а 1 ·а n – целое число, но а 1 ·а n =а n+1 +а n–1 и а n+1 =а 1 ·а n –а n–1 . Однако, а n–1 , согласно индукционному предположению, – целое. Значит, целым является и а n+1 . Следовательно, х n +1/х n – целое число при любом целом n, что и требовалось доказать.
4. Доказать, что при любом натуральном n большем 1 справедливо двойное неравенство
5. Доказать, что при натуральном n > 1 и |х|
(1–x) n +(1+x) n
При n=2 неравенство верно. Действительно,
(1–x) 2 +(1+x) 2 = 2+2·х 2
Если неравенство верно при n=k, то при n=k+1 имеем
(1–x) k+1 +(1+x) k+1
Неравенство доказано для любого натурального n > 1.
6. На плоскости дано n окружностей. Доказать, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.
Воспользуемся методом математической индукции.
При n=1 утверждение очевидно.
Предположим, что утверждение справедливо для любой карты, образованной n окружностями, и пусть на плоскости задано n+1 окружностей. Удалив одну из этих окружностей, мы получим карту, которую в силу сделанного предположения можно правильно раскрасить двумя красками (смотрите первый рисунок из приведённых ниже).
Восстановим затем отброшенную окружность и по одну сторону от нее, например внутри, изменим цвет каждой области на противоположный (смотрите второй рисунок). Легко видеть, что при этом мы получим карту, правильную раскрашенную двумя красками, но только теперь уже при n+1 окружностях, что и требовалось доказать.
7. Выпуклый многоугольник будем называть «красивым», если выполняются следующие условия:
1) каждая его вершина окрашена в один из трёх цветов;
2) любые две соседние вершины окрашены в разные цвета;
3) в каждый из трёх цветов окрашена, по крайней мере, одна вершина многоугольника.
Доказать, что любой красивый n-угольник можно разрезать не пересекающимися диагоналями на «красивые» треугольники.
Воспользуемся методом математической индукции.
База индукции. При наименьшем из возможных n=3 утверждение задачи очевидно: вершины «красивого» треугольника окрашены в три разных цвета и никакие разрезы не нужны.
Предположение индукции. Допустим, что утверждение задачи верно для любого «красивого» n-угольника.
Индукционный шаг. Рассмотрим произвольный «красивый» (n+1)-угольник и докажем, используя предположение индукции, что его можно разрезать некоторыми диагоналями на «красивые» треугольники. Обозначим через А 1 , А 2 , А 3 , … А n , А n+1 – последовательные вершины (n+1)-угольника. Если в какой-либо из трёх цветов окрашена лишь одна вершина (n+1)-угольника, то, соединив эту вершину диагоналями со всеми не соседними с ней вершинами, получим необходимое разбиение (n+1)-угольника на «красивые» треугольники.
Если в каждый из трёх цветов окрашены не менее двух вершин (n+1)-угольника, то обозначим цифрой 1 цвет вершины А 1 , а цифрой 2 цвет вершины А 2 . Пусть k – такой наименьший номер, что вершина А k окрашена в третий цвет. Понятно, что k > 2. Отсечём от (n+1)-угольника диагональю А k–2 А k треугольник А k–2 А k–1 А k . В соответствии с выбором числа k все вершины этого треугольника окрашены в три разных цвета, то есть этот треугольник «красивый». Выпуклый n-угольник А 1 А 2 … А k–2 А k А k+1 … А n+1 , который остался, также, в силу индуктивного предположения, будет «красивым», а значит разбивается на «красивые» треугольники, что и требовалось доказать.
8. Доказать, что в выпуклом n-угольнике нельзя выбрать больше n диагоналей так, чтобы любые две из них имели общую точку.
Проведём доказательство методом математической индукции.
Докажем более общее утверждение: в выпуклом n-угольнике нельзя выбрать больше n сторон и диагоналей так, чтобы любые две из них имели общую точку. При n = 3 утверждение очевидно. Допустим, что это утверждение верно для произвольного n-угольника и, используя это, докажем его справедливость для произвольного (n+1)-угольника.
Допустим, что для (n+1)-угольника это утверждение неверно. Если из каждой вершины (n+1)-угольника выходит не больше двух выбранных сторон или диагоналей, то всего их выбрано не больше чем n+1. Поэтому из некоторой вершины А выходит хотя бы три выбранных стороны или диагонали AB, AC, AD. Пусть АС лежит между АВ и AD. Поскольку любая сторона или диагональ, которая выходит из точки С и отличная от СА, не может одновременно пересекать АВ и AD, то из точки С выходит только одна выбранная диагональ СА.
Отбросив точку С вместе с диагональю СА, получим выпуклый n-угольник, в котором выбрано больше n сторон и диагоналей, любые две из которых имеют общую точку. Таким образом, приходим к противоречию с предположением, что утверждение верно для произвольного выпуклого n-угольника.
Итак, для (n+1)-угольника утверждение верно. В соответствии с принципом математической индукции утверждение верно для любого выпуклого n-угольника.
9. В плоскости проведено n прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку. На сколько частей разбивают плоскость эти прямые.
С помощью элементарных рисунков легко убедится в том, что одна прямая разбивает плоскость на 2 части, две прямые – на 4 части, три прямые – на 7 частей, четыре прямые – на 11 частей.
Обозначим через N(n) число частей, на которые n прямых разбивают плоскость. Можно заметить, что
N(2)=N(1)+2=2+2,
N(3)=N(2)+3=2+2+3,
N(4)=N(3)+4=2+2+3+4.
Естественно предположить, что
N(n)=N(n–1)+n=2+2+3+4+5+…+n,
или, как легко установить, воспользовавшись формулой суммы n первых членов арифметической прогрессии,
N(n)=1+n(n+1)/2.
Докажем справедливость этой формулы методом математической индукции.
Для n=1 формула уже проверена.
Сделав предположение индукции, рассмотрим k+1 прямых, удовлетворяющих условию задачи. Выделим из них произвольным образом k прямых. По предположению индукции они разобьют плоскость на 1+ k(k+1)/2 частей. Оставшаяся (k+1)-я прямая разобьётся выделенными k прямыми на k+1 частей и, следовательно, пройдёт по (k+1)-й части, на которые плоскость уже была разбита, и каждую из этих частей разделит на 2 части, то есть добавится ещё k+1 часть. Итак,
N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,
что и требовалось доказать.
10. В выражении х 1:х 2: … :х n для указания порядка действий расставляются скобки и результат записывается в виде дроби:
(при этом каждая из букв х 1 , х 2 , … , х n стоит либо в числителе дроби, либо в знаменателе). Сколько различных выражения можно таким образом получить при всевозможных способах расстановки скобок?
Прежде всего ясно, что в полученной дроби х 1 будет стоять в числителе. Почти столь же очевидно, что х 2 окажется в знаменателе при любой расстановке скобок (знак деления, стоящий перед х 2 , относится либо к самому х 2 , либо к какому-либо выражению, содержащему х 2 в числителе).
Можно предположить, что все остальные буквы х 3 , х 4 , … , х n могут располагаться в числителе или знаменателе совершенно произвольным образом. Отсюда следует, что всего можно получить 2 n–2 дробей: каждая из n–2 букв х 3 , х 4 , … , х n может оказаться независимо от остальных в числителе или знаменателе.
Докажем это утверждение по индукции.
При n=3 можно получить 2 дроби:
так что утверждение справедливо.
Предположим, что оно справедливо при n=k и докажем его для n=k+1.
Пусть выражение х 1:х 2: … :х k после некоторой расстановки скобок записывается в виде некоторой дроби Q. Если в это выражение вместо х k подставить х k:х k+1 , то х k окажется там же, где и было в дроби Q, а х k+1 будет стоять не там, где стояло х k (если х k было в знаменателе, то х k+1 окажется в числителе и наоборот).
Теперь докажем, что можно добавить х k+1 туда же, где стоит х k . В дроби Q после расстановки скобок обязательно будет выражение вида q:х k , где q – буква х k–1 или некоторое выражение в скобках. Заменив q:х k выражением (q:х k):х k+1 =q:(х k ·х k+1), мы получим, очевидно, ту же самую дробь Q, где вместо х k стоит х k ·х k+1 .
Таким образом, количество всевозможных дробей в случае n=k+1 в 2 раза больше чем в случае n=k и равно 2 k–2 ·2=2 (k+1)–2 . Тем самым утверждение доказано.
Ответ: 2 n–2 дробей.
Задачи без решений
1. Доказать, что при любом натуральном n:
а) число 5 n –3 n +2n делится на 4;
б) число n 3 +11n делится на 6;
в) число 7 n +3n–1 делится на 9;
г) число 6 2n +19 n –2 n+1 делится на 17;
д) число 7 n+1 +8 2n–1 делится на 19;
е) число 2 2n–1 –9n 2 +21n–14 делится на 27.
2. Докажите, что (n+1)·(n+2)· … ·(n+n) = 2 n ·1·3·5·…·(2n–1).
3. Доказать неравенство |sin nx| n|sin x| для любого натурального n.
4. Найдите натуральные числа a, b, c, которые не делятся на 10 и такие, что при любом натуральном n числа a n + b n и c n имеют одинаковые две последние цифры.
5. Доказать, что если n точек не лежат на одной прямой, то среди прямых, которые их соединяют, не менее чем n различных.
Урок № 50
Тема урока : Метод математической индукции.
Цель урока: Познакомиться с сущностью метода математической индукции, научитесь применять этот метод при решении задач на доказательство, продолжить развитие вычислительных навыков, продолжить формирование математической грамотности.
Ход урока.
Организационный момент. Постановка целей урока
Активизация опорных знаний.
Определение геометрической прогрессии, формулы n-го члена геометрической прогрессии.
Повторить формулу суммы n первых членов арифметической прогрессии.
Повторить формулу суммы бесконечно убывающей геометрической прогрессии
3. Изучение нового материала
При решении многих задач, при доказательстве справедливости математических предложений, а также при выводе формулы часто используется рассуждение, которое называется методом математической индукции.
Такое рассуждение вы, например, использовали при выводе формулы n -го члена, а также при выводе формулы суммы первых n членов арифметической и геометрической прогрессий.
Сущность этого метода заключается в следующем: если надо установить справедливость некоторого утверждения, в которой фигурирует натуральное число n , то:
1) проверяется, что предполагаемое утверждение имеет место для конкретного значения n (например для n =1).
2) предполагается, что утверждение справедливо при каком-нибудь произвольном значении n = k , и доказывается, что в таком случае оно справедливо и при n = k + 1. Отсюда делается вывод, что утверждение справедливо при любом значении n , ибо справедливость его была обнаружена при n =1, а по доказанному оно верно и при n = 2, а раз справедливо при n = 2, то справедливо и при n = 3 и т.д.
Теперь рассмотрим примеры использования данного метода.
Пример 1. Докажем, что при всяком натуральном n имеет место равенство
Формула верна для n = 1, так как:
Допустим, что формула верна при п = k .
Докажем, что в таком случае она верна и при n = k + 1, т.е.
Непосредственная проверка показала, что формула верна при n =1; следовательно, она будет справедлива также при n = 2, а потому и при n = 3, следовательно, и при п = 4 и вообще при любом натуральном n .
4.Решение задач
№249 (а)
В данной задаче требуется доказать формулу n – го члена арифметической прогрессии методом математической индукции
При n =1 имеем а 1 =а 1.
Допустим, что данная формула верна для k -го члена, т.е имеет место равенство а k = a 1 + d ( k -1)
Докажем, что в данном случае эта формула верна и для (k +1)-го члена. Действительно,
а k +1 = a 1 + d ( k +1-1) = а 1 + dk
С другой стороны, по определению ариф. прогр. а k +1 = а k + d
Так как левые части двух последних выражений равны = и правые равны:
а k + d = а 1 + dk или а k = a 1 + d ( k -1)
Полученное верное равенство позволяет утверждать, что формула n -го члена арифметической прогрессии подходит для любого натурального n
№ 255
Докажем, что число 11 n+1 +12 2 n -1 при всех натуральных значениях n делиться на 133
При n =1 имеем 11 1+1 +12 2*1-1 =133, 133 делиться на 133
Допустим, что при n = k сумма 11 k +1 +12 2 k -1 делиться на 133
Докажем, что эта сумма делиться на 133 при n = k +1, т.е. 11 k +2 +12 2 k +1 делиться на 133
11 k+2 +12 2k+1 =11*11 k +1 +144*12 k-1 =11*11 k +1 +11*12 2k-1 +133*12 2k-1 =11(11 k+1 +12 2k-1 )+133*12 2k-1
Каждое слагаемое полученной суммы делиться на 133. Следовательно, 11 k +2 +12 2 k +1 тоже делить на 133.
5. Рефлексия
6. Постановка Д/з
§15 решить №251
МБОУ лицей «Технико-экономический»
МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ.
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Методическая разработка «Метод математической индукции» составлена для обучающихся 10 класса математического профиля.
Первоочередные цели: познакомить обучающихся с методом математической индукции и научить применять его при решении различных задач.
В методической разработке рассматриваются вопросы элементарной математики: задачи на делимость, доказательство тождеств, доказательство неравенств, предлагаются задачи различной степени сложности, в том числе и задачи, предлагаемые на олимпиадах.
Роль индуктивных выводов в экспериментальных науках очень велика. Они дают те положения, из которых потом путем дедукции делаются дальнейшие умозаключения. Название метод математической индукции обманчиво – на самом деле этот метод является дедуктивным и дает строгое доказательство утверждениям, угаданным с помощью индукции. Метод математической индукции содействует выявлению связей между различными разделами математики, помогает развитию математической культуры обучающегося.
Определение метода математической индукции. Полная и неполная индукции. Доказательство неравенств. Доказательство тождеств. Решение задач на делимость. Решение различных задач по теме «Метод математической индукции».
ЛИТЕРАТУРА ДЛЯ УЧИТЕЛЯ
1. М.Л.Галицкий. Углубленное изучение курса алгебры и математического анализа. – М.Просвещение.1986.
2. Л.И.Звавич. Алгебра и начала анализа. Дидактические материалы. М.Дрофа.2001.
3. Н.Я.Виленкин. Алгебра и математический анализ. М Просвещение.1995.
4. Ю.В.Михеев. Метод математической индукции. НГУ.1995.
ЛИТЕРАТУРА ДЛЯ ОБУЧАЮЩИХСЯ
1. Н.Я.Виленкин. Алгебра и математический анализ. М Просвещение.1995.
2. Ю.В.Михеев. Метод математической индукции. НГУ.1995.
КЛЮЧЕВЫЕ СЛОВА
Индукция, аксиома, принцип математической индукции, полная индукция, неполная индукция, утверждение, тождество, неравенство, делимость.
ДИДАКТИЧЕСКОЕ ПРИЛОЖЕНИЕ К ТЕМЕ
«МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ».
Урок № 1.
Определение метода математической индукции.
Метод математической индукции является одним из высокоэффективных методом поиска новых результатов и доказательства истинности выдвинутых предположений. Хотя этот метод в математике и не нов, но интерес к нему не ослабевает. Впервые в четком изложении метод математической индукции был применен в 17 веке выдающимся французским ученым Блезом Паскалем при доказательстве свойств числового треугольника, носящего с того времени его имя. Однако идея математической индукции была известна еще древним грекам. В основе метода математической индукции лежит принцип математической индукции, который принимается как аксиома. Идею математической индукции рассмотрим на примерах.
Пример № 1.
Квадрат делится отрезком на две части, затем одна из полученных частей делится на две части и так далее. Определить, на какое число частей разделится квадрат через п шагов?
Решение.
После первого шага мы, по условию, получим 2 части. На втором шаге мы одну часть оставляем без изменений, а вторую – делим на 2 части и получаем 3 части. На третьем шаге мы 2 части оставляем без изменений, а третью делим на две части и получаем 4 части. На четвертом шаге мы 3 части оставляем без изменений, а последнюю часть делим на две части и получаем 5 частей. На пятом шаге мы получим 6 частей. Напрашивается предложение, что через п шагов мы получим (п+1) часть. Но это предложение нужно доказать. Предположим, что через к шагов квадрат разобьется на (к+1) часть. Тогда на (к+1) шаге мы к частей оставим без изменения, а (к+1) часть делим на две части и получим (к+2) части. Замечаете, что так можно рассуждать как угодно долго, до бесконечности. То есть, наше предположение, что через п шагов квадрат будет разбит на (п+1) часть, становится доказанным.
Пример № 2.
У бабушки был внучек, который очень любил варенье, и особенно то, что в литровой банке. Но бабушка не разрешала его трогать. И задумал внучек обмануть бабушку. Он решил съедать каждый день по 1/10 л из этой банки и доливать её водой, тщательно перемешав. Через сколько дней бабушка обнаружит обман, если варенье остается прежним на вид при разбавлении его водой на половину?
Решение.
Найдем, сколько чистого варенья останется в банке через п дней. После первого дня в банке останется смесь, состоящая на 9/10 из варенья и на 1/10 из воды. Через два дня из банки исчезнет 1/10 смеси воды и варенья и останется (в 1л смеси находится 9/10л варенья, в 1/10л смеси находится 9/100лваренья)
9/10 – 9/100=81/100=(9/10) 2 л варенья. На третий день из банки исчезнет 1/10л смеси, состоящей на 81/100 из варенья и на19/100 из воды. В 1л смеси находится 81/100л варенья, в 1/10л смеси 81/1000л варенья. 81/100 – 81/1000=
729/1000=(9/10) 3 л варенья останется через 3 дня, а остальное будет занимать вода. Выявляется закономерность. Через п дней в банке останется (9/10) п л варенья. Но это, опять, только наше предположение.
Пусть к – произвольное натуральное число. Предположим, что через к дней в банке останется (9/10) к л варенья. Посмотрим, что же тогда будет в банке еще через день, то есть, через (к+1) день. Из банки исчезнет 1/10л смеси, состоящей из (9/10) к л варенья и воды. В 1л смеси находится (9/10) к л варенья, в 1/10л смеси (9/10) к+1 л варенья. Теперь мы смело можем заявлять, что через п дней в банке останется (9/10) п л варенья. Через 6 дней в банке будет 531444/1000000л варенья, через 7 дней – 4782969/10000000л варенья, то есть меньше половины.
Ответ: через 7 дней бабушка обнаружит обман.
Попытаемся выделить самое основное в решениях рассмотренных задач. Каждую из них мы начинали решать с рассмотрения отдельных или, как говорят, частных случаев. Затем на основе наших наблюдений, мы высказывали некоторое предположение Р(п) , зависящее от натурального п.
утверждение проверили, то есть доказали Р(1), Р(2), Р(3);
предположили, что Р(п) справедливо при п=к и вывели, что тогда оно будет справедливо и при следующем п, п=к+1.
А затем рассуждали примерно так: Р(1) верно, Р(2) верно, Р(3) верно, Р(4) верно,…, значит верно Р(п).
Принцип математической индукции.
Утверждение Р(п) , зависящее от натурального п , справедливо при всех натуральных п , если
1) доказана справедливость утверждения при п=1;
2) из предположения справедливости утверждения Р(п) при п=к следует
справедливость Р(п) при п=к+1.
В математике принцип математической индукции выбирается, как правило, в качестве одной из аксиом, определяющих натуральный ряд чисел, и, следовательно, принимается без доказательства. Метод доказательства по принципу математической индукции обычно называется методом математической индукции. Заметим, что этот метод широко применяется при доказательстве теорем, тождеств, неравенств при решении задач на делимость и многих других задач.
Урок № 2
Полная и неполная индукция.
В случае, когда математическое утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта, например, утверждение «Каждое двузначное четное число является суммой двух простых чисел». Метод доказательства, при котором мы проверяем утверждение для конечного числа случаев, называется полной математической индукцией. Этот метод применим сравнительно редко, так как утверждения чаще всего рассматриваются на бесконечных множествах. Например, теорема «Любое четное число равно сумме двух простых чисел» до сих пор ни доказана, ни опровергнута. Если бы мы даже проверили эту теорему для первого миллиарда, это бы ни на шаг не приблизило бы нас к её доказательству.
В естественных науках применяют неполную индукцию, проверяя эксперимент несколько раз, переносят результат на все случаи.
Пример № 3.
Угадаем с помощью неполной индукции формулу для суммы кубов натуральных чисел.
Решение.
1 3 =1; 1 3 +2 3 =(1+2) 2 ; 1 3 +2 3 +3 3 =(1+2+3) 2 ; 1 3 +2 3 +3 3 +4 3 =(1+2+3+4) 2 ;
1 3 +2 3 +3 3 +4 3 +5 3 =(1+2+3+4+5) 2 ; …; 1 3 +2 3 +…+n 3 =(1+2+…+n) 2 .
Доказательство.
Пусть верно для
п=к.
Докажем, что верно для п=к+1.
Вывод: формула для суммы кубов натуральных чисел верна для любого натурального п.
Пример № 4.
Рассмотрите равенства и догадайтесь, к какому общему закону подводят эти примеры.
Решение.
1=0+1
2+3+4=1+8
5+6+7+8+9=8+27
10+11+12+13+14+15+16=27+64
17+18+19+20+21+22+23+24+25=64+125
……………………………………………………………..
Пример № 5.
Запишите в виде суммы следующие выражения:
1) 
2) 
3)
; 4) 
.
греческая буква «сигма».
Пример № 6.
Запишите следующие суммы с помощью знака 
:
2) 
Пример № 7.
Запишите следующие выражения в виде произведений:
1) 
3) 
4) 
Пример № 8.
Запишите следующие произведения с помощью знака 
(прописная греческая буква «пи»)
1) 
2)
Пример № 9.
Вычисляя значение многочлена 
f
(
n
)=
n
2
+
n
+11
, при
п=1,2,3,4.5,6,7
можно сделать предположение, что при любом натуральном
п
число
f
(
n
)
простое.
Верно ли это предположение?
Решение.
Если каждое слагаемое суммы делится на число, то сумма делится на это число, 
не является простым числом при любом натуральном
п.
Разбор конечного числа случаев играет важную роль в математике: не давая доказательства того или иного утверждения, он помогает угадать правильную формулировку этого утверждения, если она ещё неизвестна. Именно так член Петербургской академии наук Гольдбах пришел к гипотезе, что любое натуральное число, начиная с двух, является суммой не более чем трёх простых чисел.
Урок № 3.
Метод математической индукции позволяет доказывать различные тождества.
Пример № 10. Докажем, что для всех п выполняется тождество
Решение.
Положим 
Нам надо доказать, что
Докажем, что Тогда из истинности тождества
следует истинность тождества 
По принципу математической индукции доказана истинность тождества при всех п .
Пример № 11.
Докажем тождество 
Доказательство.
почленно получившиеся равенства.
; 
. Значит, данное тождество истинно для всех
п
.
Урок № 4.
Доказательство тождеств методом математической индукции.
Пример № 12.
Докажем тождество 
Доказательство.
Применяя принцип математической индукции, доказали, что равенство верно при всех п .
Пример № 13.
Докажем тождество 
Доказательство.
Применяя принцип математической индукции, доказали, что утверждение верно при любом натуральном п .
Пример № 14. Докажем тождество
Доказательство.
Пример № 15. Докажем тождество
1)
п=1;
2) для
п=к
выполняется равенство 
3) докажем, что равенство выполняется для п=к+1:
Вывод: тождество справедливо для любого натурального п.
Пример № 16. Докажем тождество
Доказательство.
Если
п=1
, то 
Пусть тождество выполняется при п=к.
Докажем, что тождество выполняется при п=к+1.
Тогда тождество справедливо для любого натурального п .
Урок № 5.
Доказательство тождеств методом математической индукции.
Пример № 17. Докажем тождество
Доказательство.
Если
п=2
, то получаем верное равенство: 
Пусть равенство верно при п=к:
Докажем справедливость утверждения при п=к+1.
Согласно принципу математической индукции, тождество доказано.
Пример № 18.
Докажем тождество 
при п≥2.
При
п=2
это тождество перепишется в очень простом виде 
и, очевидно, верно.
Пусть при п=к действительно
.
Докажем справедливость утверждения при п=к+1, то есть выполняется равенство: .
Итак, мы доказали, что тождество верно при любом натуральном п≥2.
Пример № 19. Докажем тождество
При
п=1
получим верное равенство: 
Предположим, что при п=к получаем также верное равенство:
Докажем, что наблюдается справедливость равенства при п=к+1:
Тогда тождество справедливо при любом натуральном п .
Урок № 6.
Решение задач на делимость.
Пример № 20. Доказать методом математической индукции, что
делится на 6
без остатка.
Доказательство.
При
п=1
наблюдается деление на
6
без остатка,
.
Пусть при
п=к
выражение 
кратно
6.
Докажем, что при
п=к+1
выражение 
кратно
6
.
Каждое слагаемое кратно 6 , следовательно сумма кратна 6 .
Пример № 21.
на
5
без остатка.
Доказательство.
При
п=1
выражение делится без остатка 
.
Пусть при
п=к
выражение 
также делится на
5
без остатка.
При п=к+1 делится на 5 .
Пример № 22.
Доказать делимость выражения 
на
16.
Доказательство.
При п=1 кратно 16 .
Пусть при
п=к
кратно
16.
При п=к+1
Все слагаемые делятся на 16: первое – очевидно, второе по предположению, а в третьем – в скобках стоит четное число.
Пример № 23.
Доказать делимость 
на
676.
Доказательство.
Предварительно докажем, что 
делится на 
.
При
п=0
.
Пусть при
п=к
делится на
26
.
Тогда при п=к+1 делится на 26 .
Теперь проведем доказательство утверждения, сформулированного в условии задачи.
При п=1 делится на 676.
При
п=к
верно, что 
делится на
26
2
.
При п=к+1 .
Оба слагаемых делятся на 676 ; первое – потому, что мы доказали делимость на 26 выражения, стоящего в скобках, а второе делится по предположению индукции.
Урок № 7.
Решение задач на делимость.
Пример № 24.
Доказать, что 
делится на
5
без остатка.
Доказательство.
При
п=1
делится на
5.
При
п=к
делится на
5
без остатка.
При п=к+1 каждое слагаемое делится на 5 без остатка.
Пример № 25.
Доказать, что 
делится на
6
без остатка.
Доказательство.
При
п=1
делится на
6
без остатка.
Пусть при
п=к
делится на
6
без остатка.
При
п=к+1
делится на
6
без остатка, так как каждое слагаемое делится на
6
без остатка: первое слагаемое – по предположению индукции, второе – очевидно, третье – потому, что 
четное число.
Пример № 26.
Доказать, что 
при делении на
9
дает остаток
1
.
Доказательство.
Докажем, что 
делится на
9
.
При
п=1 
делится на
9
. Пусть при
п=к
делится на
9
.
При п=к+1 делится на 9 .
Пример № 27.
Доказать, что делится на 15 без остатка.
Доказательство.
При п=1 делится на 15 .
Пусть при п=к делится на 15 без остатка.
При п=к+1
Первое слагаемое кратно
15
по предположению индукции, второе слагаемое кратно
15
– очевидно, третье слагаемое кратно
15
, так как 
кратно
5
(доказано в примере № 21), четвертое и пятое слагаемые также кратны
5
, что очевидно, тогда сумма кратна
15
.
Урок № 8-9.
Доказательство неравенств методом математической индукции
Пример № 28.
.
При п=1
имеем 
- верно.
Пусть при п=к
- верное неравенство.
При п=к+1
Тогда неравенство справедливо для любого натурального п .
Пример № 29.
Доказать, что справедливо неравенство 
при любом п
.
При п=1 получим верное неравенство 4 >1.
Пусть при п=к
справедливо неравенство 
.
Докажем, что при п=к+1
справедливо неравенство 
Для любого натурального к наблюдается неравенство .
Если 
при 
то
Пример № 30.
при любом натуральном п
и любом 
Пусть п=1
, верно.
Предположим, что неравенство выполняется при п=к
: 
.
При п=к+1
Пример № 31. Доказать справедливость неравенства
при любом натуральном п
.
Докажем сначала, что при любом натуральном т справедливо неравенство
Умножим обе части неравенства на 
. Получим равносильное неравенство или 
; 
; - это неравенство выполняется при любом натуральном т
.
При п=1
исходное неравенство верно 
; 
; 
.
Пусть неравенство выполняется при п=к:
.
При п=к+1
Урок № 10.
Решение задач по теме
Метод математической индукции.
Пример № 32. Доказать неравенство Бернулли.
Если 
, то для всех натуральных значений
п
выполняется неравенство
Доказательство.
При
п=1
доказываемое неравенство принимает вид 
и, очевидно, справедливо. Предположим, что оно верно при
п=к
, то есть что 
.
Так как по условию 
, то 
, и потому неравенство не изменит смысла при умножении обеих его частей на 
:
Так как 
, то получаем, что
.
Итак, неравенство верно при п=1 , а из его истинности при п=к следует, что оно истинно и при п=к+1. Значит, в силу математической индукции оно имеет место для всех натуральных п.
Например, 
Пример № 33.
Найти все натуральные значения
п
, для которых справедливо неравенство 
Решение.
При п=1 неравенство справедливо. При п=2 неравенство также справедливо.
При п=3 неравенство уже не выполняется. Лишь при п=6 неравенство выполняется, так что за базис индукции можно взять п=6.
Предположим, что неравенство справедливо для некоторого натурального к:
Рассмотрим неравенство
Последнее неравенство выполняется, если 
Контрольная работа по теме
п=1
задана рекуррентно: п≥5
, где п
- -натуральное число.
МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
Слово индукция по-русски означает наведение, а индуктивными называют выводы, на основе наблюдений, опытов, т.е. полученные путем заключения от частного к общему.
Например, мы каждый день наблюдаем, что Солнце восходит с востока. Поэтому можно быть уверенным, что и завтра оно появится на востоке, а не на западе. Этот вывод мы делаем, не прибегая ни к каким предположениям о причине движения Солнца по небу (более того, само это движение оказывается кажущимся, поскольку на самом деле движется земной шар). И, тем не менее, этот индуктивный вывод правильно описывает те наблюдения, которые мы проведем завтра.
Роль индуктивных выводов в экспериментальных науках очень велика. Они дают те положения, из которых потом путем дедукции делаются дальнейшие умозаключения. И хотя теоретическая механика основывается на трех законах движения Ньютона, сами эти законы явились результатом глубокого продумывания опытных данных, в частности законов Кеплера движения планет, выведенных им при обработке многолетних наблюдений датского астронома Тихо Браге. Наблюдение, индукция оказываются полезными и в дальнейшем для уточнения сделанных предположений. После опытов Майкельсона по измерению скорости света в движущейся среде оказалось необходимым уточнить законы физики, создать теорию относительности.
В математике роль индукции в значительной степени состоит в том, что она лежит в основе выбираемой аксиоматики. После того как длительная практика показала, что прямой путь всегда короче кривого или ломанного, естественно было сформулировать аксиому: для любых трех точек А, В и С выполняется неравенство
Лежащее в основе арифметики понятие следовать за тоже появилось при наблюдениях за строем солдат, кораблей и другими упорядоченными множествами.
Не следует, однако, думать, что этим исчерпывается роль индукции в математике. Разумеется, мы не должны экспериментально проверять теоремы, логически выведенные из аксиом: если при выводе не было сделано логических ошибок, то они постольку верны, поскольку истинны принятые нами аксиомы. Но из данной системы аксиом можно вывести очень много утверждений. И отбор тех утверждений, которые надо доказывать, вновь подсказывается индукцией. Именно она позволяет отделить полезные теоремы от бесполезных, указывает, какие теоремы могут оказаться верными, и даже помогает наметить путь доказательства.
Суть метода математической индукции
Во многих разделах арифметики, алгебры, геометрии, анализа приходится доказывать истинность предложений А(n), зависящих от натуральной переменной. Доказательство истинности предложения А(n) для всех значений переменной часто удается провести методом математической индукции, который основан на следующем принципе.
Предложение А(n) считается истинным для всех натуральных значений переменной, если выполнены следующие два условия:
Предложение А(n) истинно для n=1.
Из предположения, что А(n) истинно для n=k (где k - любое натуральное число), следует, что оно истинно и для следующего значения n=k+1.
Этот принцип называется принципом математической индукции. Обычно он выбирается в качестве одной из аксиом, определяющих натуральный ряд чисел, и, следовательно, принимается без доказательства.
Под методом математической индукции понимают следующий способ доказательства. Если требуется доказать истинность предложения А(n) для всех натуральных n, то, во-первых, следует проверить истинность высказывания А(1) и, во-вторых, предположив истинность высказывания А(k), попытаться доказать, что высказывание А(k+1) истинно. Если это удается доказать, причем доказательство остается справедливым для каждого натурального значения k, то в соответствии с принципом математической индукции предложение А(n) признается истинным для всех значений n.
Метод математической индукции широко применяется при доказательстве теорем, тождеств, неравенств, при решении задач на делимость, при решении некоторых геометрических и многих других задач.
Метод математической индукции в решении задач на
делимость
С помощью метода математической индукции можно доказывать различные утверждения, касающиеся делимости натуральных чисел.
Следующее утверждение можно сравнительно просто доказать. Покажем, как оно получается с помощью метода математической индукции.
Пример 1 . Если n - натуральное число, то число четное.
При n=1 наше утверждение истинно: - четное число. Предположим, что - четное число. Так как , a 2k - четное число, то и 
четное. Итак, четность доказана при n=1, из четности выведена четность 
.Значит, четно при всех натуральных значениях n.
Пример 2. Доказать истинность предложения
A(n)={число 5 кратно 19}, n - натуральное число.
Решение.
Высказывание А(1)={число кратно 19} истинно.
Предположим, что для некоторого значения n=k
А(k)={число кратно 19} истинно. Тогда, так как
Очевидно, что и A(k+1) истинно. Действительно, первое слагаемое делится на 19 в силу предположения, что A(k) истинно; второе слагаемое тоже делится на 19, потому что содержит множитель 19. Оба условия принципа математической индукции выполнены, следовательно, предложение A(n) истинно при всех значениях n.
Применение метода математической индукции к
суммированию рядов
Пример 1. Доказать формулу
, n - натуральное число.
Решение.
При n=1 обе части равенства обращаются в единицу и, следовательно, первое условие принципа математической индукции выполнено.
Предположим, что формула верна при n=k, т.е.
.
Прибавим к обеим частям этого равенства и преобразуем правую часть. Тогда получим
Таким образом, из того, что формула верна при n=k, следует, что она верна и при n=k+1. Это утверждение справедливо при любом натуральном значении k. Итак, второе условие принципа математической индукции тоже выполнено. Формула доказана.
Пример 2. Доказать, что сумма n первых чисел натурального ряда равна .
Решение.
Обозначим искомую сумму , т.е. 
.
При n=1 гипотеза верна.
Пусть 
. Покажем, что 
.
В самом деле,
Задача решена.
Пример 3.
Доказать, что сумма квадратов n первых чисел натурального ряда равна 
.
Решение.
Пусть .
.
Предположим, что 
. Тогда
И окончательно .
Пример 4. Доказать, что .
Решение.
Если , то
Пример 5. Доказать, что
Решение.
При n=1 гипотеза очевидно верна.
Пусть .
Докажем, что .
Действительно,
Примеры применения метода математической индукции к
доказательству неравенств
Пример 1. Доказать, что при любом натуральном n>1
.
Решение.
Обозначим левую часть неравенства через .
Следовательно, при n=2 неравенство справедливо.
Пусть при некотором k. Докажем, что тогда и . Имеем 
, .
Сравнивая и , имеем 
, т.е. 
.
При любом натуральном k правая часть последнего равенства положительна. Поэтому . Но , значит, и .
Пример 2. Найти ошибку в рассуждении.
Утверждение. При любом натуральном n справедливо неравенство .
Доказательство.
. (1)
Докажем, что тогда неравенство справедливо и при n=k+1, т.е.
.
Действительно, не меньше 2 при любом натуральном k. Прибавим к левой части неравенства (1) , а к правой 2. Получим справедливое неравенство , или 
. Утверждение доказано.
Пример 3.
Доказать, что 
, где >-1, , n - натуральное число, большее 1.
Решение.
При n=2 неравенство справедливо, так как .
Пусть неравенство справедливо при n=k, где k - некоторое натуральное число, т.е.
. (1)
Покажем, что тогда неравенство справедливо и при n=k+1, т.е.
. (2)
Действительно, по условию, , поэтому справедливо неравенство
, (3)
полученное из неравенства (1) умножением каждой части его на . Перепишем неравенство (3) так: . Отбросив в правой части последнего неравенства положительное слагаемое , получим справедливое неравенство (2).
Пример 4. Доказать, что
(1)
где , , n - натуральное число, большее 1.
Решение.
При n=2 неравенство (1) принимает вид
. (2)
Так как , то справедливо неравенство
. (3)
Прибавив к каждой части неравенства (3) по , получим неравенство (2).
Этим доказано, что при n=2 неравенство (1) справедливо.
Пусть неравенство (1) справедливо при n=k, где k - некоторое натуральное число, т.е.
. (4)
Докажем, что тогда неравенство (1) должно быть справедливо и при n=k+1, т.е.
(5)
Умножим обе части неравенства (4) на a+b. Так как, по условию, , то получаем следующее справедливое неравенство:
. (6)
Для того чтобы доказать справедливость неравенства (5), достаточно показать, что
, (7)
или, что то же самое,
. (8)
Неравенство (8) равносильно неравенству
. (9)
Если , то , и в левой части неравенства (9) имеем произведение двух положительных чисел. Если , то , и в левой части неравенства (9) имеем произведение двух отрицательных чисел. В обоих случаях неравенство (9) справедливо.
Этим доказано, что из справедливости неравенства (1) при n=k следует его справедливость при n=k+1.
Метод математической индукции в применение к другим
задачам
Наиболее естественное применение метода математической индукции в геометрии, близкое к использованию этого метода в теории чисел и в алгебре, - это применение к решению геометрических задач на вычисление. Рассмотрим несколько примеров.
Пример 1. Вычислить сторону правильного - угольника, вписанного в круг радиуса R.
Решение.
При n=2 правильный 2 n - угольник есть квадрат; его сторона . Далее, согласно формуле удвоения
находим, что сторона правильного восьмиугольника 
, сторона правильного шестнадцатиугольника 
, сторона правильного тридцатидвухугольника 
. Можно предположить поэтому, что сторона правильного вписанного 2
n
- угольника при любом равна
. (1)
Допустим, что сторона правильного вписанного - угольника выражается формулой (1). В таком случае по формуле удвоения
,
откуда следует, что формула (1) справедлива при всех n.
Пример 2. На сколько треугольников n-угольник (не обязательно выпуклый) может быть разбит своими непересекающимися диагоналями?
Решение.
Для треугольника это число равно единице (в треугольнике нельзя провести ни одной диагонали); для четырехугольника это число равно, очевидно, двум.
Предположим, что мы уже знаем, что каждый k-угольник, где k
А n
А 1 А 2
Пусть А 1 А k - одна из диагоналей этого разбиения; она делит n-угольник А 1 А 2 …А n на k-угольник A 1 A 2 …A k и (n-k+2)-угольник А 1 А k A k+1 …A n . В силу сделанного предположения, общее число треугольников разбиения будет равно
(k-2)+[(n-k+2)-2]=n-2;
тем самым наше утверждение доказано для всех n.
Пример 3. Указать правило вычисления числа P(n) способов, которыми выпуклый n-угольник может быть разбит на треугольники непересекающимися диагоналями.
Решение.
Для треугольника это число равно, очевидно, единице: P(3)=1.
Предположим, что мы уже определили числа P(k) для всех k
Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n-1).
С помощью этой формулы последовательно получаем:
P(4)=P(3)+P(3)=2,
P(5)=P(4)+P(3)P(3)+P(4)+5,
P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14
и т.д.
Так же при помощи метода математической индукции можно решать задачи с графами.
Пусть на плоскости задана сеть линий, соединяющих между собой какие-то точки и не имеющие других точек. Такую сеть линий мы будем называть картой, заданные точки ее вершинами, отрезки кривых между двумя смежными вершинами - границами карты, части плоскости, на которые она разбивается границами - странами карты.
Пусть на плоскости задана некоторая карта. Мы будем говорить, что она правильно раскрашена, если каждая ее страна закрашена определенной краской, причем любые две страны, имеющие между собой общую границу, закрашены в разные цвета.
Пример 4. На плоскости дано n окружностей. Доказать, что при любом расположении этих окружностей образуемую ими карту можно правильно раскрасить двумя красками.
Решение.
При n=1 наше утверждение очевидно.
Предположим, что наше утверждение справедливо для любой карты, образованной n окружностями, и пусть на плоскости задано n+1 окружностей. Удалив одну из этих окружностей, мы получим карту, которую в силу сделанного предположения можно правильно раскрасить двумя красками, например черной и белой.
