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

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

В математике важно иметь точные формулы, позволяющие вычислять сумму различных последовательностей чисел. В данном случае мы хотим вывести формулу, дающую сумму первых n натуральных чисел.

Например, «сумма» всего лишь одного первого натурального числа 1 равна 1; сумма двух первых натуральных чисел 1+2 равна 3, сумма первых трех натуральных чисел 1+2+3 равна 6, сумма первых четырех натуральных чисел 1+2+3+4 равна 10 и т. д.

Возможно, что требуемая формула имеет вид

?(n) = ?·n(n + 1).

Иначе говоря, если требуется найти сумму n первых натуральных чисел, то нужно просто подставить число n в приведенную выше формулу и получить ответ.

Доказательство по индукции позволяет убедиться в том, что эта формула дает правильный ответ при любом натуральном числе от 1 до бесконечности. Первый шаг состоит в том, чтобы показать, что формула работает в первом случае, при n=1. В этом нетрудно убедиться непосредственно, так как мы знаем, что сумма, состоящая из одного-единственного слагаемого, числа 1, равна 1. Подставляя n=1 в нашу формулу убеждаемся в том, что она дает правильный результат:

?(1) = ?·1·(1 + 1).

Следующий шаг в доказательстве по индукции заключается в том, чтобы показать, что если формула верна при каком-то значении n, то она должна быть верна и при n+1. Если

?(n) = ?·n(n + 1).

то

?(n + 1) = ?(n) + (n + 1) = ?·n(n + 1) + (n + 1).

После преобразования членов в правой части получаем

?(n + 1) = ?·(n + 1)[(n + 1) + 1].

Важно отметить, что последняя формула «устроена» точно так же, как исходная формула с той лишь разницей, что там, где в исходной формуле стоит n, в новой формуле стоит n+1. Иначе говоря, если формула верна для n, то она должна быть верна и для n+1. Доказательство по индукции завершено.