Вот объяснение на примере:
Допустим, у вас есть следующая формула, которую вы хотите доказать:
sum(i | i <- [1, n]) = n * (n + 1) / 2
Эта формула предоставляет закрытую форму для суммы всех целых чисел от 1 до n.
Начнем с доказательства формулы для простого базового случая n = 1. В этом случае обе части формулы уменьшаются до 1. Это, в свою очередь, означает, что формула верна для n = 1.
Далее мы докажем, что если формула верна для значения n, то она верна для следующего значения n (или n + 1). Другими словами, если верно следующее:
sum(i | i <- [1, n]) = n * (n + 1) / 2
Тогда верно и следующее:
sum(i | i <- [1, n + 1]) = (n + 1) * (n + 2) / 2
Для этого давайте начнем с первой части последней формулы:
s1 = sum(i | i <- [1, n + 1]) = sum(i | i <- [1, n]) + (n + 1)
То есть сумма всех целых чисел от 1 до n + 1 равна сумме целых чисел от 1 до n плюс последний член n + 1.
Поскольку мы основываем это доказательство на условии, что формула выполняется для n, мы можем написать:
s1 = n * (n + 1) / 2 + (n + 1) = (n + 1) * (n + 2) / 2 = s2
Как видите, мы подошли ко второй части формулы, которую мы пытаемся доказать, что означает, что формула действительно верна.
Это завершает индуктивное доказательство, но что это на самом деле означает?
- Формула верна для n = 0.
- Если формула верна для
n, то она верна для n + 1.
Из 1 и 2 можно сказать: если формула верна для n = 0, то она верна для 0 + 1 = 1. Поскольку мы доказали случай n = 0, то случай n = 1 действительно верен.
Мы можем повторить этот процесс снова. Случай n = 1 является правильным, тогда случай n = 2 является правильным. Это рассуждение может идти до бесконечности; формула верна для всех целочисленных значений n> = 1.