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

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

План лекции:

1. Понятие индукции и дедукции

2. Дедуктивный и индуктивный методы

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

Понятие индукции и дедукции

В основе всякого научного исследования, в том числе и математического, лежат дедуктивный и индуктивный методы.

Дедукция (от лат. deductio - выведение) – это переход от общего к частному.

Индукция (от лат. inductio — наведение) – это вид обобщений, полученный путем заключения от частного к общему.

Дедуктивный и индуктивный методы

Дедуктивный метод в математике применяется, например, в рассуждениях: «данная фигура является прямоугольником, так как у каждого прямоугольника диагонали равны, следовательно, и у данного прямоугольника диагонали равны».

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

работает для конечного множества, исследует не все, а лишь

в котором можно проверить некоторые элементы

все элементы множества

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

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

Принцип математической индукции заключается в следующем.

Утверждение P(n) справедливо для всякого натурального n, если:

1. Оно справедливо для n=1 или для наименьшего из натуральных чисел, при котором закономерность имеет смысл.

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

Алгоритм доказательства методом математической индукции.

1. БАЗА. Проверяют справедливость гипотезы для наименьшего из натуральных чисел, при котором гипотеза имеет смысл (базис). Для этого нужно подставить наименьшее число в данное выражение и, если левая часть окажется равной правой, то этот этап доказан.

2. ПРЕДПОЛОЖЕНИЕ. Сделать предположение, что гипотеза верна для некоторого значения n=k. Здесь подставляется в данное выражение замена и полученное выражение будем считать формулой и будем её применять в 3 пункте.

3. ДОКАЗАТЕЛЬСТВО. Будем доказывать справедливость данного выражения для n=k+1. Для этого подставим эту замену в данную выражение так, чтобы n-ый член и (n+1)-ый член присутствовали в левой части. Затем, формулу из 2 части (предположения) нужно применить к левой части полученного выражения. В итоге получится новое выражение, которое упрощается так, чтобы получились две одинаковые части – левая и правая или 0=0.

4. ВЫВОД. Если такое доказательство удалось довести до конца, то, на основе принципа математической индукции можно утверждать, что высказанная гипотеза справедлива для любого натурального числа n.

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

Пример. Доказать, что для любого натурального n справедливо равенство:

Решение:

1. БАЗА.Проверим равенство при n=1. Имеем , 1=1 – значит, формула верна.

2. ПРЕДПОЛОЖЕНИЕ. Предположим, что данная формула справедлива для n=k, то есть

. Полученное выражение будем считать формулой и будем её применять в 3 пункте

1. ДОКАЗАТЕЛЬСТВО. Докажем, что формула верна для n=k+1. Подставим эту замену в данную функцию так, чтобы присутствовали и n-ый член и (n+1)-ый член, то есть имеет место выражение

Воспользуемся формулой из 2 пункта (вместо левой части формулы подставим правую часть), то есть

Имеем новое выражение

Упростим это выражение, приведя к общему знаменателю, выражение примет вид

после преобразования получим

1. ВЫВОД. Видим, что формула справедлива для n=k+1 при условии ее выполнимости при n=k, следовательно, она справедлива для любого натурального числа n.

Задания для самостоятельной работы

1. Переписать лекцию в тетрадь или распечатать и вклеить, разобрать её

1. Изучить алгоритм доказательства методом математической индукции

1. Следующие выражения доказать методом математической индукции:

1. 

2. (x-число, а работать нужно с n)

Пользуясь этим и теоретическим материалом учебника М.С. Спирина «Дискретная математика» глава 5 п.5.6 стр.262-276, выполнить все задания.