II. Актуализация знаний, умений и навыков.
Знаменитый математик XVII в. П.Ферма проверив, что числа
, 
, 
, 
, 
простые, сделал по индукции предположение, что для всех n=1,2,3,… числа вида простые.
В XVIII веке Л.Эйлер нашел, что при n=5:
составное число
III. Изучение новой темы
1. Дедуктивный и индуктивный метод
В основе всякого математического исследования лежат дедуктивный и индуктивный методы. Дедуктивный метод рассуждений - это рассуждение от общего к частному, т.е. рассуждение, исходным моментом которого является общий результат, а заключительным моментом – частный результат.
Слово индукция по-русски означает наведение, а индуктивными называют выводы, сделанные на основе наблюдений, опытов, т.е. полученные путем заключения от частного к общему.
2. Полная и неполная индукция
Метод математической индукции можно сравнить с прогрессом. Мы начинаем с низшего, в результате логического мышления приходим к высшему. Человек всегда стремился к прогрессу, к умению развивать свою мысль логически, а значит, сама природа предначертала ему размышлять индуктивно.
Пусть требуется установить, что каждое натуральное чётное число 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.
Эти девять равенств показывают, что каждое из интересующих нас чисел действительно представляется в виде суммы двух простых слагаемых.Таким образом, полная индукция заключается в том, что общее утверждение доказывается по отдельности в каждом из конечного числа возможных случаев.
Иногда общий результат удаётся предугадать после рассмотрения не всех, а достаточно большого числа частных случаев (так называемая неполная индукция).Результат, полученный неполной индукцией, остается, однако, лишь гипотезой, пока он не доказан точным математическим рассуждением, охватывающим все частные случаи. Иными словами, неполная индукция в математике не считается законным методом строгого доказательства, но является мощным методом открытия новых истин.
3. Метод математической индукции
Вообразим очередь, где первой стоит женщина, за ней снова женщина, а за ней снова женщина. Верно ли, что все стоящие в очереди — женщины?
Конечно, верно! Раз первые три человека в очереди — женщины, то, скорее всего, это очередь за косметикой, или за чем-нибудь таким, в чём нуждаются и разбираются исключительно женщины, и мужчин в этой очереди нет.
Рассмотрим два утверждения:
- Первый человек в очереди есть женщина.
- За женщиной в очереди может стоять только женщина.
Из этих двух утверждений строго следует, что в очереди стоят только женщины. Мы можем последовательными шагами показать, что любой человек в очереди — женщина.
Таким образом, метод математической индукции заключается в следущем:
Пусть нужно доказать справедливость некоторого утверждения для любого натурального числа n (например нужно доказать, что сумма первых n нечётных чисел равна n2). Непосредственная проверка этого утверждения для каждого значения n невозможна, поскольку множество натуральных чисел бесконечно. Чтобы доказать это утверждение, проверяют сначала его справедливость для n=1. Затем доказывают, что при любом натуральном значении k из справедливости рассматриваемого утверждения при n=k вытекает его справедливость и при n=k+1.Тогда утверждение считается доказанным для всех n.
4. Примеры
Ханойские башни
Есть три стержня и 
колец разного размера. Класть можно только кольцо меньшего размера на кольцо большего размера. Можно ли переместить пирамидку с одного стержня на другой?
- Пирамидку, в которой только одно кольцо n=1, переместить можно (очевидно).
- Предположим, что мы умеем перемещать пирамидки с числом колецn≤k.
- Попробуем научиться перемещать пирамидку с n=k+1. Пирамидку из kколец, лежащих на самом большом k+1-м кольце, мы можем согласно предположению переместить на любой стержень. Сделаем это, переместим её на третий стержень. Неподвижное k+1-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое. После перемещения kколец переместим оставшееся k+1-е кольцо на второй стержень. Мы можем это сделать, так как второй стержень пустой. Теперь обратим внимание, тот факт, что второй стержень не пустой, не мешает нам класть на него любые кольца, так как имеющееся на нём кольцо самое большое (любое кольцо можно положить на большее, а значит и самое большое по условию задачи). И затем опять применим известный нам по предположению алгоритм перемещения kколец и переместим их на второй стержень, стержень с лежащим внизу k+1-м кольцом. Таким образом, если мы умеем перемещать пирамидки с
кольцами, то умеем перемещать пирамидки и с k+1 кольцом. - Следовательно утверждение верно для всех случаев, то есть для всех .
Заметим, что всё решение было разбито на четыре этапа:
- [БАЗА] Показываем, что доказываемое утверждение верно для некоторых простейших частных случаев (в нашей задачке это был случай n=1)
- [ПРЕДПОЛОЖЕНИЕ] Предполагаем, что утверждение доказано для первых kслучаев.
- [ШАГ] В этом предположении доказываем утверждение для случаяn=k+1.
- [ВЫВОД] Утверждение верно для всех случаев, то есть для всехn.
Пересечение прямых
Докажите, что любые прямых, расположенных на одной плоскости, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в 
точках.
Решение:
1. [БАЗА] В простейшем случае, когда прямых две, известно, что они непаралельны, а значит пересекаются как минимум в одной точке.
2.[ПРЕДПОЛОЖЕНИЕ] Предположим, что оно верно для k прямых, то есть что любые kпрямых, никакие две из которых не параллельны, и никакие три не пересекаются в одной точке, пересекаются ровно в 
точках.
3.[ШАГ] Попробуем доказать его для k+1 прямых. По предположению, 1-я, 2-я, …, k-я прямая пересекаются в 
точках. Рассмотрим k+1-ю прямую и одну из прямых, обозначим её iиз списка 1-я, 2-я, …, k-я прямая. Как мы уже доказали в [БАЗЕ] любые две прямые, удовлетворяющие условиям задачи, пресекаются ровно в одной точке, а значит и прямые k+1и iпересекаются в одной точке. Вспомним, что iобозначает любую прямую из списка 1-я, 2-я, …, k. Отсюда k+1-я прямая пересекается с каждой из этих kпрямых ровно в одной точке.
Рассмотрим список из k+1 прямых и их точек пересечения. Уберём прямуюk+1 вместе с её точками пересечения. Останется kпрямых удовлетворяющих [ШАГУ]. Значит количество точек пересечения у этих kпрямых равняется 
. Как было показано выше, количество точек пересечения, которое мы убрали вместе с прямой k+1, равняется k.
Следовательно, количество точек пересечения всех k+1 прямых есть 
.
То есть для k+1прямых утверждение доказано.
4.[ВЫВОД] Утверждение верно для любого количества прямых.
3) Докажите тождество 
.
Доказательство. Проверим, работает ли эта формула при n=1:
1. [БАЗА] 
.
2.[ПРЕДПОЛОЖЕНИЕ] Предположим, что тождество верно при n=k, то есть
3.[ШАГ] Шаг индукции будет соответствовать проверке этого тождества при n=k+1, то есть нужно доказать, что
.
4.[ВЫВОД] Тождество верно для любого .
IV. Отработка знаний, умений и навыков по теме.
Класс разбивается на 4 группы. В каждой группе назначается координатор, который будет оказывать помощь остальным участникам группы.
Группа 1.
Задача 1. Докажите, что при каждом натуральном , начиная с 
, существует выпуклый -угольник, имеющий ровно три острых угла.
Задача 2. Доказать, что 1+3+5+…+(2n-1)=n 2 .
Задача 3. Доказать, что (11 n+2 +12 2n+1 ) делится на 133 без остатка.
Группа 2.
Задача 1. Плоскость разделена на части прямыми. Докажите, что эти части можно раскрасить в два цвета так, что соседние куски будут раскрашены в разные цвета.
Задача 2. Доказать, что 1+х+х 2 +х 3 +…+х n =(х n+1 -1)/(х-1).
Задача 3. Доказать, что при любом n 7 n -1 делится на 6 без остатка.
Группа 3.
Задача 1. Докажите что сумма углов выпуклого -угольника равна 
, (или 
радиан). В частности для треугольника получаем 
, а для четырехугольника — 
Задача 2. Доказать, что при любом n справедливо утверждение: 1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6.
Задача 3. Доказать, что 3 3n-1 +2 4n-3 при произвольном натуральном n делится на 11.
Группа 4.
Задача 1. Чему равно количество кусочков, на которые прямых (не проходящих через одну точку) делят плоскость на части? Одна прямая — на две части, две — на четыре. А пятнадцать прямых?
Задача 2. Доказать, что 1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3) для любого натурального n.
Задача 3. Доказать, что 11 2n -1 при произвольном натуральном n делится на 6 без остатка.
