Inducción: la cadena de fichas de dominó

Una demostración directa funciona cuando puedes ver todo el razonamiento de una vez, como la división en casos de la lección anterior. Se derrumba en el momento en que la afirmación contiene tres puntos. La suma de uno a n tiene infinitas instancias, y ninguna página contiene infinitas líneas. Escribir y así sucesivamente no es una demostración, es la promesa de que existe una en algún sitio. La inducción es la herramienta que cumple esa promesa con un número finito de palabras, y tiene exactamente dos partes.

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

El caso base es la afirmación con el menor n permitido sustituido dentro, comprobada a mano. El paso inductivo es una condicional: suponiendo que la afirmación se cumple para un n, demuestra que entonces se cumple para n más uno. Fíjate en lo que el paso no hace. No dice nada sobre si la afirmación es cierta para ningún n concreto. Es una máquina que convierte una verdad en n en una verdad en n más uno, y una máquina sin entrada no produce salida. Juntas, las dos partes lo dan todo: el caso base arranca la cadena y el paso la arrastra hacia adelante para siempre.

Aquí está por qué hacen falta las dos mitades, y merece la pena ver un fallo real de cada tipo en lugar de aceptarlo por fe. Primero, el paso solo. Si supones que n más uno es igual a n y sumas uno a ambos lados, obtienes n más dos igual a n más uno, que es la misma afirmación con n sustituido por n más uno. El paso es perfectamente válido. La afirmación sigue siendo falsa para todo n, porque ninguna primera ficha llegó a caer.

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

Ahora el otro fallo: un caso base sin paso que funcione. El polinomio de abajo se creyó de verdad que era primo para todo n, y se cumple en n igual a uno. Incluso sobrevive hasta n igual a 39. En n igual a 40 se factoriza, y ahí se detiene la cadena. Este es el fallo que te encuentra en el código: cien índices de un arreglo se portan bien, y el índice cero o el último nunca estuvieron en el rango que probaste.

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

A veces suponer solo el caso n no basta. Si descompones un número en dos factores menores, necesitas saber que ambos se descomponen en primos, y los dos son menores que n en lugar de iguales a n menos uno. La inducción fuerte supone la afirmación para todo valor por debajo de n, lo que da más material y no es en realidad un requisito más fuerte: todo lo demostrable por inducción fuerte lo es por inducción ordinaria, solo que con un enunciado más torpe. En la práctica la distinción importa porque la inducción fuerte es la forma correcta para dividir y vencerás.

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)

Esto nos lleva a la razón de que esta lección esté en un curso de programación. La ordenación por mezcla se llama a sí misma dos veces sobre mitades y mezcla los resultados. Los estudiantes suelen aceptar que funciona porque han visto que funciona. La razón real es la demostración inductiva. Caso base: un arreglo de longitud cero o uno está ordenado, y la función lo devuelve. Paso: supongamos que la ordenación por mezcla devuelve un arreglo ordenado para toda entrada más corta que n. Entonces las dos mitades vuelven ordenadas, y mezclar dos arreglos ordenados da un arreglo ordenado. Por inducción la función es correcta para arreglos de cualquier longitud. Esto no es adorno: el caso base de abajo es exactamente la condición del if, y el paso es exactamente la corrección de 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)Ordenación por mezcla recursiva. El caso base de la inducción es la primera línea y el paso inductivo es la mezcla.

La misma forma da el tiempo de ejecución, y de aquí sale por fin O(log n), en lugar de ser una forma que se memoriza de una gráfica. En cada nivel de recursión el trabajo total es n, y el número de niveles es cuántas veces puedes dividir n por la mitad antes de llegar a un elemento, es decir el logaritmo de n en base 2. Multiplica el trabajo por nivel por el número de niveles y obtienes n log n. La búsqueda binaria es el caso más afilado: hace trabajo constante por nivel y tira la mitad de los datos, así que el coste es exactamente el número de divisiones por la mitad. Duplicar la entrada añade un paso, y por eso una búsqueda sobre un millón de elementos necesita veinte comparaciones y no un millón. La inducción hace que esta frase sea cierta en lugar de solo observada.

/* 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)