Técnicas de demostración

1) Método directo

Supones la hipótesis y, encadenando definiciones y resultados previos, llegas a la conclusión. Ejemplo: «la suma de dos enteros pares es par». Sean 2m y 2n; su suma es 2m + 2n = 2(m + n), que es 2 por un entero, o sea par. Fin (QED).

2) Contrarrecíproco

Para probar «si P entonces Q», es equivalente probar «si no Q entonces no P». Cuando negar Q te da más información útil que asumir P, este método brilla. Ejemplo: «si n² es par, entonces n es par». Contrarrecíproco: «si n es impar, n² es impar», que es fácil de verificar.

3) Reducción al absurdo (contradicción)

Supones la negación de lo que quieres probar y derivas una contradicción lógica. El clásico: √2 es irracional. Supón que es a/b irreducible; acabas concluyendo que a y b son ambos pares, contradicciendo que fuera irreducible. Luego la suposición era falsa.

4) Inducción matemática

Para probar una propiedad P(n) para todo entero n ≥ 1, dos pasos: (base) P(1) es cierta, y (paso inductivo) si P(k) es cierta entonces P(k+1) lo es. Como fichas de dominó: tiras la primera, y cada ficha tira a la siguiente.

¿Por qué le importa esto a un científico de datos? La corrección de algoritmos recursivos y iterativos se prueba por inducción: la «invariante de bucle» es literalmente una hipótesis inductiva. Y la complejidad de un algoritmo divide-y-vencerás (merge sort) se resuelve con recurrencias que se verifican por inducción.