Метод математической индукции

Разработчики очень часто имеют дело с рекурсивными функциями. В моем случае чаще на курсах, на работе реже, но и там они тоже попадаются. Раньше, создавая очередную рекурсивную функцию, я не задумывался о доказательстве того, что она будет корректно работать для всех валидных для нее входящих данных, достаточно и тестов на пограничные и средние значения. Но недавно, на курсе Introduction to Computer Science and Programming Using Python, я познакомился с методом математической индукции, с помощью которого, в некоторых случаях, можно именно доказать, что функция будет корректно работать для всего множество входящих данных, если это - натуральные числа. Сам метод показался занимательным, но, в то же время, очень простым и сподвиг меня на написание данной статьи.

Принцип математической индукции формулируется следующим образом:
утверждение P(n), где n - натуральное число, справедливо для любого n из множества N, если:

• утверждение P(n) справедливо наименьшего n, т.е. при n = 0 или n = 1
• для любого k из множества N при справедливости утверждения P(k), справедливо и P(k + 1)

Доказательство посредством математической индукции проводится в два этапа:

1. Базис индукции: доказательство, что P(1) верно
2. Шаг индукции: считая справедливым P(k), доказываем справедливость P(k + 1)

Чтобы более полно понять, давайте посмотрим небольшой пример.

Определим функцию sum-numbers с параметром x, которая считает сумму ряда натуральных чисел от 0 до x:

Теперь докажем, что она правильно работает для всех натуральных чисел:

Проверим базис: (sum-numbers 0) = 0 - верно.

Теперь перейдем к шагу индукции:

допустим выражение (sum-numbers k) корректно, докажем, что и (sum-numbers k+1) также корректно.
Минимальное значение k - это ноль, поэтому k + 1 > 0, соответственно внутри if мы попадаем в
(+ x (sum-numbers (- x 1)))
в нашем случае, это будет равно:
(+ (+ k 1) (sum-numbers (- (+ k 1) 1)))
немного упрощаем и получаем
(+ (+ k 1) (sum-numbers k)))
По условию (sum-numbers k) отрабатывает корректно, и является суммой для ряда натуральных чисел от 0 до k, а k + 1 - это следующее число в этом ряду. В итоге мы имеем, что и для (k + 1) функция считает верно.
Основываясь на этих двух утверждениях, можно сказать, что данная функция будет правильно работать для всех натуральных чисел.