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

Краснодарский край         Лабинский район станица Вознесенская

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

Работа

 Голованёвой Ксении Сергеевны, ученицы 9 «Б» класса муниципального общеобразовательного учреждения средней школы №28 станицы Вознесенской муниципального образования Лабинский район Краснодарского края

Руководитель:

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

Аннотация.

Слово индукция по-русски означает наведение, а индуктивными называют выводы, сделанные на основе наблюдений, опытов, т.е. полученные путем заключения от частного к общему. В основе всякого математического исследования лежат дедуктивный и индуктивный методы. Дедуктивный метод рассуждений - это рассуждение от общего к частному, т.е. рассуждение, исходным моментом которого является общий результат, а заключительным моментом – частный результат. Индукция применяется при переходе от частных результатов к общим, т.е. является методом, противоположным дедуктивному. Одним из самых универсальных методов доказательств математических утверждений и решения задач, в которых фигурируют слова «для произвольного натурального n» (возможно, явно не высказанное), является метод математической индукции, который можно  сравнить с прогрессом. Мы начинаем с низшего, в результате логического мышления приходим к высшему. Человек всегда стремился к прогрессу, к умению развивать свою мысль логически, а значит, сама природа предначертала ему размышлять индуктивно. Актуальность выбранной нами темы  заключается в том, что возросла область применения метода математической индукции (математика, химия, физика, логика и т.д.), однако из школьной программы он практически исключен. Изучается в основном на факультативных занятиях, где на это отводится мало времени: рассматривается содержание метода и применение его к решению примитивных задач.

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

Исследовательские задачи:

- рассмотреть понятия полной и  неполной индукции;

- изучить принцип математической индукции;

- изучить метод математической индукции;

- исследовать применение метода математической индукции к решению задач:

на суммирование и делимость,

на доказательство неравенств и тождеств,

геометрических задач.

Полная и неполная индукция.

По своему первоначальному смыслу слово «индукция» применяется к рассуждениям, при помощи которых получают общие выводы, опираясь на ряд частных утверждений. Простейшим методом рассуждений такого рода является полная индукция. Вот пример подобного рассуждения.

Пусть требуется установить, что каждое натуральное чётное число n в пределах 4≤ n≤ 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:

4=2+2;  6=3+3;  8=5+3;  10=7+3;  12=7+5;

14=7+7;  16=11+5;  18=13+5;  20=13+7.

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

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

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

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

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

Во многих случаях выход из такого рода затруднений заключается в обращении к особому методу рассуждений, называемому методом математической индукции. Он заключается в следующем.

Пусть нужно доказать справедливость некоторого утверждения для любого натурального числа n (например нужно доказать, что сумма первых n нечётных чисел равна n2). Непосредственная проверка этого утверждения для каждого значения n невозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это утверждение, проверяют сначала его справедливость для n=1. Затем доказывают, что при любом натуральном значении k из справедливости рассматриваемого утверждения при n=k вытекает его справедливость и при n=k+1.Тогда утверждение считается доказанным для всех n.

Обобщая сказанное, сформулируем следующий общий принцип.

Принцип математической индукции.

   Для перехода от частных результатов, справедливых для отдельных значений n, к общим, верным при всех n, пользуются принципом математической индукции.   Имеется некоторое утверждение А, зависящее определенным образом от натурального аргумента n, который принимает все целые положительные значения, начиная от р. Чтобы доказать справедливость утверждения А, поступают следующим образом:

1. убеждаются в справедливости А при n=р;
2. предполагают, что А верно при всех n, для которых p< n≤  k;
3. используя п.1 и 2, доказывают, что утверждение А справедливо при n=k+1.

Выполнение требований 1 – 3 позволяет от значения n=p, которое берется минимальным из всех возможных, шаг за шагом переходить к значениям р+1, р+2 и т.д. Поэтому считают, что выполнение требований 1 – 3 влечет за собой справедливость утверждения А для всех n >  р. Это одна из аксиом натуральных чисел. Она называется аксиомой индукции.

В ряде случаев бывает нужно доказать справедливость некоторого утверждения не для всех натуральных чисел, а лишь для n ≥ p, где p-фиксированное натуральное число. В этом случае принцип математической индукции формулируется следующим образом:

Если предложение А(n) истинно при n=p и если А(k)→ А(k+1) для любого k ≥ p, то предложение А(n) истинно для любого n ≥ p.

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

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

На заре теории чисел математики открыли многие факты индуктивным путём: Л.Эйлер и К.Гаусс рассматривали подчас тысячи примеров, прежде чем подметить числовую закономерность и поверить в неё. Но одновременно они понимали, сколь обманчивыми могут быть гипотезы, прошедшие «конечную» проверку. Числа Ферма Fk =22k+1 оказались простыми при k=0, 1, 2, 3, 4, но у F5 Эйлер обнаружил делитель. Числа Мерсанна Mp=2p-1, где p-простые числа, сами являются простыми при p=2, 3, 5, 7, но не при p=11(а потом вновь  будут простыми при p=13, 17, 19,…).Лейбниц думал какое-то время, что n2k+1 –n делится на 2k+1, проверив это при k=1, 2, 3. Но при k=4 это не так.            

Итак, для индуктивного перехода от утверждения, проверенного для конечного подмножества, к аналогичному утверждению для всего бесконечного множества необходимо доказательство. Но как осуществить проверку бесконечного числа  случаев? Такой способ предложили Б.Паскаль и Я.Бернулли. Теперь он носит название метода математической индукции.

 Пусть некоторое свойство надо доказать для элементов последовательности

 a1, a2, …, ak, … Тогда достаточно :

1)проверить это утверждение для a1 (этот шаг называется основанием или базисом индукции);

2)из предположения, что утверждение справедливо для ak, надо доказать его справедливость для ak+1 (индуктивный переход).  

После проведения этих рассуждений можно сделать вывод, что доказываемое утверждение справедливо для всех an.

Таким образом, если предложение А(n), зависящее от натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любого натурального числа n.

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

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

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

Применение метода математической индукции

Задачи на суммирование.

Пример 1. Доказать, что 1+3+5+…+(2n-1)=n2.

Решение: 1) Имеем n=1=12. Следовательно, утверждение верно при n=1, т.е. А(1) истинно.

2) Докажем, что А(k)→ A(k+1).

Пусть k-любое натуральное число и пусть утверждение справедливо для n=k, т.е.

1+3+5+…+(2k-1)=k2.

Докажем, что тогда утверждение справедливо и для следующего натурального числа n=k+1, т.е. что

1+3+5+…+(2k+1)=(k+1)2.

В самом деле,

1+3+5+…+(2k-1)+(2k+1)=k2+2k+1=(k+1)2.

Итак, А(k)→ А(k+1). На основании принципа математической индукции заключаем, что предположение А(n) истинно для любого n € N.

Пример 2. Доказать, что

1+х+х2+х3+…+хn = (хn+1-1)/(х-1), где х≥ 1

Решение: 1) При n=1 получаем

1+х = (х2-1)/(х-1) = (х-1)(х+1)/(х-1) = х+1

следовательно, при n=1 формула верна; А(1) истинно.

2) Пусть k-любое натуральное число и пусть формула верна при n=k, т.е.

1+х+х2+х3+…+хk = (хk+1-1)/(х-1).

Докажем, что тогда выполняется равенство

1+х+х2+х3+…+хk+xk+1 = (xk+2-1)/(х-1).

В самом деле

1+х+х2+x3+…+хk+xk+1 = (1+x+x2+x3+…+xk)+xk+1 = (xk+1-1)/(x-1)+xk+1 = (xk+2-1)/(x-1).

Итак, А(k)→ A(k+1). На основании принципа математической индукции заключаем, что формула верна для любого натурального числа n.

Пример 3.Доказать, что13-23+33-43+…+(2n-1)3-(2n)3=-n2(4n+3) для любого натурального n.

Решение: 1) Пусть n=1, тогда

13-23=-13(4+3); -7=-7.

2) Предположим, что n=k, тогда

13-23+33-43+…+(2k-1)3-(2k)3=-k2(4k+3).

3) Докажем истинность этого утверждения при n=k+1

(13-23+…+(2k-1)3-(2k)3)+(2k+1)3-(2k+2)3=-k2(4k+3)+

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

Доказана и справедливость равенства при n=k+1, следовательно утверждение верно для любого натурального n.

Пример4. Доказать, что любую сумму денег, большую 7 копеек, можно разменять только трехкопеечными и пятикопеечными монетами.

Решение: Пусть сумма равна n копейкам. Если n=8, то утверждение верно. Пусть оно верно для n=k. Могут представиться только два случая для размена суммы в k копеек:

а) потребовались только трехкопеечные монеты,

б) потребовалась хотя бы одна пятикопеечная монета.

В случае а) удаляем 3 трехкопеечные монеты, добавляем 2 пятикопеечные и тем самым размениваем сумму в k+1 копеек. В случае б) удаляем 1 пятикопеечную монету и добавляем 2 трехкопеечные монеты, тем самым размениваем  сумму в k+1 копеек.

Задачи на доказательство неравенств.

Пример 1. Доказать неравенство Бернулли  (1+х)n ≥1+n х, х>-1, n € N.

Решение: 1) При n=1 неравенство справедливо, так как

1+х≥1+х

2) Предположим, что неравенство верно для некоторого n=k, т.е.

(1+х)k≥1+k x.

 Умножив обе части неравенства  на положительное число 1+х, получим

(1+x)k+1≥(1+k x)(1+ x)=1+(k+1) x + k x2

Учитывая, что k x2 ≥0, приходим к неравенству

     (1+х)k+1≥1+(k+1) x.

Таким образом, из допущения, что неравенство Бернулли верно для n=k, следует, что оно верно для n=k+1. На основании метода математической индукции можно утверждать, что неравенство Бернулли справедливо для любого   n € N.

Пример 2. Доказать, что при n>6 справедливо неравенство  3n>n 2n+1.

Решение: Перепишем неравенство в виде

(3/2)n>2n.

1. При n=7 имеем

37/27=2187/128>14=2× 7

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

2. Предположим, что при n=k

(3/2)k >2k.

3) Докажем верность неравенства при n=k+1.

3k+1/2k+1=(3k/2k)× (3/2)>2k× (3/2)=3k>2(k+1).

Так как k>7, последнее неравенство очевидно.

В силу метода математической индукции неравенство справедливо для любого натурального n.

Задачи на делимость.

Пример 1. Доказать, что (11n+2+122n+1) делится на 133 без остатка.

Решение: 1) Пусть n=1, тогда

113+123=(11+12)(112-132+122)=23× 133.

Но (23× 133) делится на 133 без остатка, значит при n=1 утверждение верно; А(1) истинно.

2) Предположим, что (11k+2+122k+1) делится на 133 без остатка.

3) Докажем, что в таком случае

(11k+3+122k+3) делится на 133 без остатка. В самом деле 11k+3+122л+3=11×11k+2+

+122  ×122k+1=11× 11k+2+(11+133)× 122k+1=11(11k+2+122k+1)+133× 122k+1.

Полученная сумма делится на 133 без остатка, так как первое её слагаемое делится на 133 без остатка по предположению, а во втором одним из множителей выступает 133.

 Итак, А(k)→ А(k+1). В силу метода математической индукции утверждение доказано.

Пример 2. Доказать, что при любом n  7n-1 делится на 6 без остатка.

Решение: 1) Пусть n=1, тогда Х1=71-1=6 делится на 6 без остатка. Значит, при n=1 утверждение верно.

2) Предположим, что при  n=k  7k-1 делится на 6 без остатка.

3) Докажем, что утверждение справедливо для n=k+1.

Xk+1=7k+1-1=7× 7k-7+6=7(7k-1)+6.

Первое слагаемое делится на 6, поскольку 7k-1 делится на 6 по предположению, а вторым слагаемым является 6. Значит 7n-1 кратно 6 при любом натуральном n. В силу метода математической индукции утверждение доказано.

Пример 3. Доказать, что 33n+3-26n-27 при произвольном натуральном n делится на 262 (676) без остатка.

Решение: Предварительно докажем, что 33n+3-1 делится на 26 без остатка.

1. При n=0

33-1=26 делится на 26

2. Предположим, что при n=k

33k+3-1 делится на 26

3. Докажем, что утверждение верно при n=k+1.

33k+6-1=27× 33k+3-1=26× 33л+3+(33k+3-1) –делится на 26

Теперь проведём доказательство утверждения, сформулированного в условии задачи.

1) Очевидно, что при n=1 утверждение верно

33+3-26-27=676

2) Предположим, что при  n=k  выражение 33k+3-26k-27 делится на 262 без остатка.

3) Докажем, что утверждение верно при n=k+1

33k+6-26(k+1)-27=26(33k+3-1)+(33k+3-26k-27).

Оба слагаемых делятся на 262: первое делится на 262, потому что мы доказали делимость на 26 выражения, стоящего в скобках, а второе -  по предположению индукции. В силу метода математической индукции утверждение доказано.

                                 Задачи на доказательство тождеств.

Пример 1. Доказать, что

           1×1!+2×2!+…+n× n!=(n+1)!-1.

1) При n=1 имеем     1×1!=2!-1, т.е. 1=1; формула справедлива.

2) Предположим, что данная формула справедлива при всех n таких, что 1 < n ≤ k.

3) Докажем эту формулу для  n = k+1, т.е. установим, что верна формула

                      1×1!+2×2!+…+k×k!+(k+1)(k+1)!=(k+2)!-1, которая получается из данной заменой n на k+1.

Действительно,

 (1×1!+2×2!+…+k×k!)+(k+1)(k+1)!= (k+1)!-1+(k+1)(k+1)!=(k+1)!(k+2)-1=(k+2)!-1.

           В этой цепочке равенств при переходе от первого выражения ко второму использовано условие 2. Так как условия 1-3 выполнены, то в силу аксиомы индукции следует, что рассматриваемая формула верна при всех натуральных n.

Пример 2. Доказать тождество (формулу Муавра)

(r(cos a + i sin a))n =rn (cos na + i sin na).

1. Для n=1 тождество очевидно.
2. Пусть оно верно при 1(r(cos a + i sin a))k =rk (cos ka + i sin ka).
3. Тогда (r(cos a + i sin a))k+1 =(r (cos a + i sin a))k(r (cos a + i sin a))=

=(rk (cos ka + i sin ka))(r (cos a + i sin a)).

По правилу перемножения комплексных чисел, записанных в тригонометрической форме, имеем

(rk (cos ka + i sin ka))(r (cos a + i sin a))= rk+1 (cos (k+1)a + i sin (k+1)a),

откуда следует доказываемая формула.

Геометрическая задача.

Пример 1.  Доказать, что сумма внутренних углов выпуклого n-угольника равна π(n – 2).

1) Минимальное число углов – три. Поэтому индукция начинается с n=3. Для треугольника формула дает π(3 – 2)=π, т.е. она справедлива.

2) Допустим, что для любого выпуклого n-угольника с числом углов 3

3) Докажем ее для любого выпуклого (k+1)-угольника.

Возьмем три последовательные вершины  А, В, С (k+1)-угольника и проведем диагональ АС (рис.1). Она разобьет (k+1)-угольник на k-угольник Р и треугольник АВС, сумма внутренних углов которых равна сумме внутренних углов данного (k+1)-угольника.

Т.к. условия 1 и 2 выполнены, то

π(k - 2) + π = π(k - 1).

То же самое мы должны были бы получить из доказываемой формулы при n=k+1.

Таким образом, раскрыв содержание метода математической индукции, мы убедились, что с помощью него действительно легко решаются сложные задачи различного содержания. В основном это  логические и занимательные задачи, т.е. как раз те, которые повышают интерес к самой математике как к науке. Решение таких задач становится увлекательным занятием и может привлечь в математические лабиринты всё новых любознательных. А это является основой любой науки.

Продолжая изучать  метод математической индукции, необходимо научиться применять его не только в математике, но и в решении проблем физики, химии  и самой жизни.

Список литературы:

1. В.Г. Болтянский, Ю.В. Сидоров, М.И. Шабунин. «Математика». Лекции, задачи, решения. ООО «Попурри», 1996г.
2. И.Т. Демидов, А.Н. Колмогоров, С.И. Шварцбург, О.С. Ивашев-Мусатов, Б.Е. Вейц. «Алгебра и начала анализа». Учебное пособие. М., «Просвещение», 1975г.
3. А.А. Рывкин, А.З. Рывкин, Л.С. Хренов. «Справочник по математике». М.,   «Просвещение», 1987г
4. «Энциклопедический словарь юного математика».  Составитель А.П. Савин. М., «Педагогика», 1985г.
5. И.Ф. Шарыгин. «Факультативный курс по математике. Решение задач». М., «Просвещение», 1989г.
6. А.Д. Кутасов, Т.С. Пиголкина, В.И. Чехлов, Т.Х. Яковлева. «Пособие по математике для поступающих в вузы». М., «Наука», 1988г.