Принцип полной математической индукции

Аксиома индукции служит для обоснования мощного метода доказательства теорем, который основан на следующем утверждении.

• 2.1.4. Теорема. (Принцип полной математической индукции.) Предложение Т (п) с переменной neN верно для любого натурального числа п, если выполнены следующие условия.
• 1) Это предложение верно для п = 1, то есть Г (1) истинно.
• 2) Каково бы ни было натуральное число п, из предположения о том, что это предложение верно для п, следует, что оно верно для непосредственно следующего натурального числа п, то есть если Т (п) истинно, то и Т (п') истинно.

Доказательство. Обозначим через М множество всех натуральных чисел, для которых Т (п) истинно:

Из условия 1) следует, что 1 еМ. Пусть натуральное число пеМ. Тогда Т (п) истинно и, по условию 2), должно быть истинно Т (п'), а значит пеМ. Таким образом, оба условия аксиомы индукции Р_А выполнены, следовательно, М = N. Но это и означает, что Т (п) верно для любого п е N. ?

Доказательство на основании принципа полной математической индукции называется доказательством методом полной математической индукции. При этом, говорят кратко: докажем Т (п)

индукцией по л. Проверка истинности утверждения Г (1) называется началом индукции, предположение об истинности Г (л) называется индуктивным предположением, а доказательство истинности Г (л'), исходя из истинности Т (п), называется шагом индукции. Эта терминология восходит к наглядному представлению о процессе доказательства по индукции, изображенному на рисунке 8.

Рис. 8.

Начало Шаг индукции

индукции

Приведем типичный пример доказательства по индукции и обсудим технику записи доказательства.

Пример. Докажите, что сумма первых п нечетных натуральных чисел равна п².

В нашем случае утверждение ГО?) имеет вид:

Доказательство.

• 1) л = 1. Проверим, что 1=1. Очевидно, это равенство верно.
• 2) Пусть 1 + 3 + 5 +…+ (2л -1) = л².

Докажем, что 1+3 + 5 + …+ (2л + 1) = (л + 1)². Имеем:

и.п.

1 + 3 + 5 + .,+(2л-1) + (2и + 1) = л² + (2я + 1) = (л + 1)². ?

Выделенный курсивом текст составляет «бланк доказательства». Если убрать все остальное, то «бланк» готов для нового заполнения — доказательства нового утверждения. В пункте 1) запись Г (1) получается из предложения Г (л) формальной заменой всюду л на 1. В пункте 2) запись «пусть … докажем, что…» понимается как «пусть Г (л) истинно для фиксированного л, докажем, что Г (л + 1) истинно». При этом, Г (л + 1) получается из Г (л) чисто формально: заменой л на л + 1. Момент использования индуктивного предположения полезно выделять, помечая буквами «и.п.». Преобразования после использования индуктивного предположения можно охарактеризовать как «подгонка под ответ», так как. речь идет о получении заранее сформулированного результата. Такая стандартизация доказательства по индукции позволяет выполнять его почти автоматически. Единственный момент, требующий размышлений, — это «подгонка под ответ».

Упражнения

1. Докажите, что каждая из приведенных ниже систем удовлетворяет аксиомам Пеано, а значит является натуральным рядом.

2. Запишите аксиомы Пеано с помощью символов математической логики.

«(л + 1).

3. Докажите, что сумма первых «натуральных чисел равна —-—, сумма.

«(«+ 1)(2и +1).

квадратов первых п натуральных чисел равна — и сумма кубов.

«²(«+ 1)²

первых п натуральных чисел равна —-. Заметим, что из первого и третьего угверждений получаем тождество аль-Караджи (X в.): I³ + 2³+…+и³ = (1 + 2+…+")².

4. Докажите, что для любого натурального числа п:

• 5. Индукцией по «докажите формулу Муавра:
  • (cosa + / sina)^w = cos"a + / sin па.
• 6. Индукцией по а докажите, что для любых натуральных чисел а и b существуют целые неотрицательные числа q и г такие, что a = bq + r, причем О йг<�Ь.
• 7. Докажите, что для любого действительного числа дг > 0 и любого натурального п

_П1— а + а->+…+а_п

8. Докажите, что qaa2—a_n й-, где Я|, а₂> —. ;

положительные действительные числа. (Указание. Для перехода от «к «+ 1 докажите, что из предположения об истинности формулы для «следует истинность ее для 2п и для п -1. Для перехода от п к п -1 найдите число л*.

U] 4- +ЛГ (1 + в2+.1.

такое, что —-= =-).

п п -1.

9. Найдите ошибку в «доказательстве» того, что все натуральные числа равны. Для доказательства этого неверного утверждения индукцией по п докажем, что «в любом и-элементном подмножестве натуральных чисел все числа равны между собой». Очевидно, утверждение верно при п = 1. Пусть оно верно для п, докажем его для //-hi. Рассмотрим произвольное (и +1) -элементное подмножество натуральных чисел М = {<�ц, я₂" — * ^ап> ^ап+1} • По индуктивному предположению все числа подмножества —, <*_я,} равны между собой и равны числу а_п. Также по индуктивному предположению все числа подмножества {<�зг₂" •••"^ап> ^ап+1} равны между собой и равны числу а_п. Следовательно, все числа подмножества М равны между собой. Утверждение доказано.