Индукция: цепочка домино

Прямое доказательство работает, когда всё рассуждение видно сразу, как разбор случаев в прошлом уроке. Оно ломается в тот момент, когда в утверждении появляется многоточие. Сумма от единицы до n имеет бесконечно много частных случаев, и ни одна страница не вместит бесконечно много строк. Написать «и так далее» — не доказательство, а обещание, что доказательство где-то есть. Индукция — инструмент, который выполняет это обещание конечным числом слов, и состоит она ровно из двух частей.

claim: for every integer n >= 1,

  1 + 2 + 3 + ... + n  =  n * (n + 1) / 2

n = 1    1            = 1
n = 2    1 + 2        = 3
n = 3    1 + 2 + 3    = 6
n = 4    1+2+3+4      = 10

base case:      n = 1
inductive step: if it holds for n, it holds for n + 1

База — это утверждение с подставленным наименьшим допустимым n, проверенное руками. Индуктивный переход — условное утверждение: предполагая, что утверждение верно для некоторого n, показать, что тогда оно верно и для n + 1. Заметьте, чего переход не делает. Он ничего не говорит о том, верно ли утверждение для какого-то конкретного n. Это машина, превращающая истину при n в истину при n + 1, а машина без входа не выдаёт выхода. Вместе две части дают всё: база запускает цепочку, а переход несёт её дальше бесконечно.

Вот почему нужны обе половины; и лучше увидеть настоящий отказ каждого рода, чем поверить на слово. Сначала один переход. Если предположить, что n + 1 равно n, и прибавить к обеим частям единицу, получится n + 2 равно n + 1 — то же утверждение с n, заменённым на n + 1. Переход полностью корректен. Утверждение при этом ложно для всех n, потому что первая костяшка так и не упала.

claim A: for every integer n >= 1,  n + 1 = n

step: n + 1 = n
      (n + 1) + 1 = n + 1          holds

base: n = 1  ->  1 + 1 = 1       false

step = T, base = F

Теперь другой отказ: база есть, перехода нет. В простое ниже действительно верили для всех n, и при n равном единице оно проходит. Оно доживает даже до n = 39. При n = 40 оно разлагается, и цепочка обрывается. Это тот самый отказ, который находит вас в коде: сто индексов массива ведут себя прекрасно, а нулевой или последний никогда не попадали в протестированный диапазон.

claim B: for every integer n >= 1,  n^2 + n + 41  is prime

base: n = 1   ->  43              prime
step: n = 39  ->  1601            prime
      n = 40  ->  1681 = 41 * 41   composite

base = true, step broken at 39 -> 40

Иногда предположения только о случае n недостаточно. Если разложить число на два меньших множителя, нужно знать, что каждый из них раскладывается на простые, а они меньше n, и не обязательно равны n - 1. Сильная индукция предполагает утверждение для всех значений меньше n: это даёт больше материала и при этом не является более сильным требованием — всё, что доказывается сильной индукцией, доказывается и обычной, просто формулировка выходит неуклюжей. На практике различие важно потому, что сильная индукция — правильная форма для «разделяй и властвуй».

claim: every integer n >= 2 factors into primes

base:        n = 2 is prime
strong step: assume the claim for every k, 2 <= k < n

  n prime    ->  done
  n = a * b  ->  a < n and b < n
                 T(k) holds for 2 <= k < n

T(n) = T(a) and T(b)

Отсюда и причина, по которой этот урок стоит в курсе по программированию. Сортировка слиянием вызывает себя дважды на половинах и сливает результаты. Студенты обычно принимают, что она работает, потому что видели, как она работает. Настоящая причина — индукционное доказательство. База: массив длины ноль или один отсортирован, и функция возвращает его как есть. Переход: предположим, что сортировка слиянием возвращает отсортированный массив для любого входа короче n. Тогда обе половины возвращаются отсортированными, а слияние двух отсортированных массивов отсортировано. По индукции функция корректна для массивов любой длины. Это не украшение: база ниже — в точности условие в if, а переход — в точности корректность merge.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

# T(1) = c
# T(n) = 2 * T(n / 2) + O(n)
# depth = log2(n), work per level = O(n) -> O(n log n)Рекурсивная сортировка слиянием. База индукции — первая строка, индуктивный переход — слияние.

Та же схема даёт время работы — и именно отсюда наконец берётся O(log n), а не из формы графика, которую заучивают. На каждом уровне рекурсии суммарная работа равна n, а число уровней — это сколько раз n можно поделить пополам до одного элемента, то есть логарифм n по основанию 2. Умножаем работу на уровень на число уровней и получаем n log n. Двоичный поиск — более резкий случай: он делает постоянную работу на уровне и выбрасывает половину данных, поэтому стоимость равна ровно числу делений пополам. Удвоение входа добавляет один шаг — вот почему поиск по миллиону элементов требует двадцати сравнений, а не миллиона. Индукция делает это предложение истинным, а не просто наблюдаемым.

/* sorted array, search space halved */

  1000000  ->  500000  ->  250000  ->  125000  ->  ...

  2^10  = 1024             10 halvings
  2^20  = 1048576          20 halvings

T(1) = 1
T(n) = T(n / 2) + c   ->   T(n) = O(log n)

/* loop invariant over a[0 .. n - 1] */

init:  i = 0,  m = a[0]
test:  while i < len(a):
step:    if a[i] > m: m = a[i]
         i = i + 1
exit:  i == len(a)  ->  m = max(a)