Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Сущность метода математической индукции (МИ)



Впервые был применен для строгих доказательств в 1575 году итальянским ученым Франческа Мауролико. В начале XVII столетия Пьер де Ферма усовершенствовал этот метод и назвал его методом бесконечного спуска. Понятие «математическая индукция» была введена де Морганом в начале XIX века.

Математическая индукция как метод проверки правильности программирования для компьютеров был применен американским ученым Робертом Флайдом в 1967г. Фактически же идея индуктивных утверждений в начальном виде появилась еще в 1946г., когда Х.Гольстайн и Джон фон Нейман определили понятие блок-схемы программы.

Рассмотрим ММИ на примере анализа утверждения о целом числе n. Пусть P(n)-некоторое утверждение о числе n.

P1(n)=”n(n+3)-четное число”

P2(n)=”если n≥10, то 2n≥n3

Предположим что мы хотим доказать что P(n)справедливо для всех положительных чисел n.

Суть доказательства по ММИ состоит в следующем:

· Доказать что P(1)-справедливо

· Дать доказательство того, что если P(1),P(2),…P(n)-справедливо, то справедливо P(n+1).

В качестве примера приведем соотношение известное с древних времен

1=12, 1+3=22, 1+3+5=32, 1+3+5+7=42, 1+3+5+7+9=52, …(*)

В общем виде это отношение можно записать 1+3+…(2n-1)=n2 (**)

Докажем это равенство с помощью ММИ, т.е. докажем что P(n) справедливо для всех положительных n. В соответствии с ММИ имеем:

· P(1)=1-верно 1=12

· Если все утверждения P(1),P(2),…,P(n)-верны то выполняется соотношение(**). Добавим к обоим частям равенства (**) следующие слагаемые, которые необходимо проверить, получим 1+3+…+2n-1+2n+1=n2+2n+1=(n+1)2

Что показывает что P(n+1) также верно.






Дата публикования: 2015-03-26; Прочитано: 310 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...