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

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

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

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

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

P₂(n)=”если n≥10, то 2ⁿ≥n³”

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

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

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

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

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

1=1², 1+3=2², 1+3+5=3², 1+3+5+7=4², 1+3+5+7+9=5², …(*)

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

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

• P(1)=1-верно 1=1²

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

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

9. Построение доказательства по методу ми.

I1: [Доказать Р(1)] Положить k=1 и согласно п а) выдать доказательство утверждения Р(1).

I2: [k=n?] Если k=n то алгоритм заканчивает работу и требуемое доказательство выдано, если k≠n то:

I3: [доказать Р(k+1)] Согласно пункту б) выдать доказательство того, что если P(1), P(2), …P(k) верны, то что P(k+1) также верно и сделать соответствующий вывод.

I4: [увеличить k] k k+1 и перейти на шаг I2

Формула оценки времени выполнения алгоритма Евклида: T_n=(12*Ln(2)/п²)*Ln(n)

Блок схема алгоритма I(k=n)

(доказательство по методу математической индукции, которая заканчивается на шаге k=n)

Очевидно, что этот алгоритм дает док-во утверждения P(n) для любого заданного n и тем самым мы получаем обоснование техники док-ва по методу МИ.

10. Примеры доказательств с использованием метода ми.

Пусть задана последовательность чисел Фибоначчи

0,1,1,2,3,5,8,13,21,34,55,89…F(n)(каждое следующее число равно сумме двух предыдущих)

Обозначим - золотое сечение.

Доказать что F_n≤Ф^n-1 (*)

Доказательство: если n=1, то F_n=1

F₁=Ф^n-1=Ф⁰=1 соотношение (*) выполняется для n=1.Тем самым выполнен пункт а) в построении доказательства по методу МИ.

Если n=2 F₂=1<1,6(округленное)<Ф¹=Ф^2-1

Для n=2 соотношение (*) выполняется

Если P(1),P(2),…P(n) справедливы и n>1, то справедливы в частности P(n-1) и P(n). Получим P(n+1):

F_n-1 ≤Ф^n-2 , F_n ≤Ф^n-1

F_n+1 = F_n-1 +F_n≤Ф^n-2+Ф^n-1= Ф^n-2(1+Ф¹) (**)

1+Ф=?.Докажем что 1+Ф=Ф² (***)

Используя (***) и (**) получим F(n+1)≤Ф^n-2*Ф²=Фⁿ, т.е. F_n+1≤Фⁿ.Тем самым мы выполнили пункт б) .В данном доказательстве мы выполнили пункт б) двумя разными способами:

1.Непосредственно доказали P(n+1) при n=1,т.е. доказали P(2)

2.Использовали предположение индукции при n>1 здесь мы были вынуждены так поступить, т.к. при n=1 ссылка на P(0)=P(n-1) была бы не законной, т.к. мы начинали доказательство с n=1, а не с n=0.