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

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 и тем самым мы получаем обоснование техники док-ва по методу МИ.