Название: Доказательство правильности программ - Конспект лекций (Веретельникова Е.Л.)

Жанр: Экономика

Просмотров: 1605


1.1. принцип простой индукции

 

Пусть S(n) – некоторое высказывание о целом числе n и требуется доказать, что S(n) справедливо для всех положительных чисел n.

Согласно простой математической индукции, для этого необходимо

1) доказать, что справедливо высказывание S(1);

2) доказать, что если для любого положительного числа n справедливо высказывание S(n), то справедливо и высказывание S(n + 1).

Из приведенных выше двух утверждений вытекает, что S(n) справедливо для всех положительных чисел. Этот факт интуитивно очевиден, хотя при аксиоматической трактовке целых чисел сам принцип в такой формулировке следует рассматривать как аксиому. Из первого положения индукции следует, что справедливо S(1), а из второго – что справедливо S(2), если справедливо S(1). Но S(1) справедливо, следовательно, должно быть справедливо и S(2). Из второго положения индукции вытекает также, что справедливо S(3), если справедливо S(2). Таким образом, поскольку мы знаем, что S(2) справедливо, то, следовательно, справедливо S(3), и т. д. Отсюда интуитивно видно, что эти два положения вместе доказывают справедливость S(1), S(2), S(3), ..., S(n)....

Рассмотрим пример использования простой индукции.

Пример 1.1. Мы хотим доказать, что для любого положительного числа n сумма первых n положительных целых чисел равна n(n + 1)/2, т.е. 1 + 2 + ... + n = n (n + 1)/2 для любого положительного числа n. Используя простую индукцию, необходимо только доказать, что

1) «сумма» верна для n = 1, т.е. 1 = 1(1 + 1)/2. Это очевидно;

2) если сумма первых n положительных целых чисел равна

n(n + 1)/2, то сумма первых n + 1 положительных целых чисел равна (n + 1)[(n + 1) + 1]/2, т.е. мы предполагаем, что формула

1 + 2 + ... + n = n(n + 1)/2 справедлива. Это гипотеза индукции. На ее основании мы должны попытаться доказать, что справедлива формула

1 + 2 + ... + n + (n + 1) = (n + 1)[(n + 1) + 1]/2.

Докажем это следующим образом:

1 + 2 + ... + n + (n + 1) = (1 + 2 + ... + n) + (n + 1) =

= [n(n + 1)/2] + (n + 1) = [(n2 + n)/2] + (n + 1) =

    (По гипотезе индукции)

= [(n2 + n)/2] + [(2n + 2)/2] = (n2 + 3n + 2)/2 =

= (n + 1)(n + 2)/2 = (n + 1) ∙ [(n + 1) + 1]/2.

Что и требовалось доказать.

Поскольку мы доказали справедливость двух утверждений, то по индукции формула

1 + 2 + ... + n = n(n + 1)/2

считается справедливой для любого положительного числа n.