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

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

Математическая индукция представляет собой некоторый общий способ доказательства в математике. Он, хотя об этом не всегда явно говорят, положен в основу всех приемов доказательства правильности программ для вычислительных машин. Данная глава знакомит читателя с математической индукцией – фундаментальным способом доказательства в математике.

Обычно математическую индукцию вводят как метод доказательства утверждений о положительных числах. В данном пособии сформулированы и проиллюстрированы на примерах самые простые версии этого метода – простая и строгая индукция, необходимые для понимания сути методов доказательства правильности программ. Обобщение этого метода на случай любых вполне упорядоченных множеств рассмотрено в других учебных пособиях [1], [3].

Простая индукция

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

Пусть 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. Мы хотим доказать, что для любого поло­жительного числа п сумма первых л положительных целых чисел равна п • (п + 1)/2, т. е.

1+2 + ...+ N=N• (N+1)/2

для любого положительного числа N. Используя простую индукцию, неооходимо только доказать, что

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

2. Если сумма первых п положительных целых чисел равна п • (п + 1)/2, то сумма первых п+L положительных целых чисел равна (п +1) • [(п + 1)+1]/2, т. е. мы предпола­гаем, что формула 1 + 2 + ...+ N = п • (п + 1)/2, справедлива. Это гипотеза индукции. На ее основании мы должны по­пытаться доказать, что справедлива формула

1 + 2 + ...+ N + (п +1) = (п +1) • [(п + 1)+1]/2.

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

1 + 2 + ...+ N + (п +1) = (1 + 2 + ...+ N )+ (п +1) =

[п • (п + 1)/2] + (п +1) =[(п² + п)/2] + (п +1) =

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

[(п² + п)/2] + [(2п + 2)/2] =( п² + 3п + 2)/2 =

(п + 1) • (п + 2)/2 = (п +1) • [(п + 1)+1]/2.

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

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