Лекция 14

ТЕМА: МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

1. Понятие индукции. Аксиома математической индукции.

2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых

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

4. Обобщение метода математической индукции

Главная

1. Понятие индукции. Аксиома математической индукции

Все утверждения можно разделить на общие и частные. На­пример, утверждение «Во всяком параллелограмме диагонали делятся в точке пересечения пополам» является общим, так как относится ко всему множеству параллелограммов. В то же время утверждение «В параллелограмме ABCD диагонали в точке пе­ресечения делятся пополам» является частным утверждением, так как относится к конкретному параллелограмму ABCD.

На основе частных утверждений делают некоторые предполо­жения (гипотезы) о справедливости какого-либо общего утверж­дения. Иногда эти предположения оказываются верными, иногда неверными. Переход от частных утверждений к общим называют индукцией (от латинского слова inductio — наведение). Напри­мер, знаменитый математик XVII в. П. Ферма, проверив, что

числа

простые, сделал по индукции предположение, что для всех п = 1, 2, ... числа вида - простые. Однако это предполо­жение оказалось неверным, так как в XVIII в. Л. Эйлер нашел, что — составное число. Как видим, индукция не является методом доказательства, а лишь помогает сформулировать неизвестный результат в виде некото­рой гипотезы, справедливость которой потом надо доказать.

В случае, когда утверждение касается конечного числа объектов, его можно доказать, проверяя для каждого объекта. Например, утверждение «Каждое чет­ное однозначное число является суммой двух простых чисел» легко проверить, рассмотрев равенства 2=1 + 1, 4 = 3+1, 6 = 5+1, 8 = 3 + 5.

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

Индуктивные гипотезы формулируются обычно в виде утвер­ждений, относящихся ко всем натуральным числам. Последова­тельная проверка такого утверждения для каждого натурально­го числа п, начиная с 1, разумеется, невозможна, если говорить обо всех натуральных числах. Но сама идея последовательного перехода от натурального числа п к следующему за ним числу n +1 осуществляется в строгой форме в одном из самых важных методов математических доказательств, называемом методом математической индукции. В основе этого метода лежит аксиома индукции:

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

1) оно справедливо для n =1;

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

Действительно, из того, что утверждение верно при n= 1, вы­текает по второму условию его справедливость для n= 1 + 1 = 2, но тогда оно верно и для n = 2 + 1=3, n = 3+1= 4 и т. д. Ясно, что в конце концов мы дойдем до любого натурального числа n.

Сам метод математической индукции состоит в следующем:

Для доказательства справедливости P(n) для любого n (P(n) – есть одноместный предикат от n, значит, доказываем nP(n)  1)

1. проверить истинность при n = 1, т.е. Р(1) = 1(истина);

2. допускают, что Р(n) = 1 при n = k и

3. проверяют истинность для n = k + 1.

Если P(k + 1) = 1, то nP(n)  1.