Como provar o infinito?

Quarenta acertos, e falso

Pegue a expressão $n^2+n+41$. Para $n=0$ ela dá 41, que é primo. Para $n=1$, 43: primo. Dois, três, quatro, cinco: primo, primo, primo, primo — e isso continua quarenta vezes seguidas. Aí você testa $n=40$:

$$40^2+40+41=1681=41\times 41.$$

Quarenta confirmações não valeram nada. (O polinômio é de Euler, de 1772, e o primeiro fracasso — conferido aqui, número a número — é em $n$ = 40, onde ele vale 1.681. Não por acaso: com $n=40$, $n^2+n=40\times 41$, e o 41 aparece em tudo.)

O problema é que “sempre” é uma palavra grande. A fórmula $1+2+\cdots +n=\frac{n(n+1)}{2}$ dá para testar com 1, 2, 3, um milhão de valores — e depois do último teste sempre sobra outro número. Como provar infinitas afirmações com um argumento que cabe numa página?

O dominó

A resposta tem o formato de uma fileira de dominós. Você não precisa empurrar cada peça com a mão; precisa de duas garantias: o primeiro dominó cai, e qualquer dominó que cair derruba o seguinte. Se as duas valem, a fileira inteira vai ao chão, não importa o tamanho.

Troque os dominós por afirmações. Chame de $P(n)$ a afirmação que você quer provar:

1. Caso base: prove $P(1)$.
2. Passo indutivo: para um $k$ qualquer, suponha $P(k)$ e mostre $P(k+1)$.

$$P(1)\wedge (\forall k:P(k)\Rightarrow P(k+1))⟹\forall n:P(n).$$

E aqui está o ponto que mais confunde: no passo, você não está supondo aquilo que quer provar. Está provando uma ligação — se um caso qualquer é verdadeiro, o seguinte também é. A ligação sozinha não afirma nada sobre número nenhum; é o caso base que a põe em movimento. Tire uma das duas e tudo desmonta: um primeiro dominó que ninguém empurra deixa a fileira em pé (o passo funciona, mas nunca começa); um buraco no meio interrompe a queda (começou, mas não atravessa).

A soma dos ímpares

Some os ímpares em ordem: $1$, $1+3=4$, $1+3+5=9$, mais 7 dá 16. Os quadrados perfeitos, sem pular nenhum. E dá para ver o motivo: para transformar um quadradinho num quadrado de lado 2, faltam três peças; para chegar ao lado 3, faltam cinco; depois sete. Cada moldura nova é exatamente o próximo ímpar:

$$1+3+5+\cdots +(2n-1)=n^2.$$

O desenho convence para os quadrados que dá para desenhar; a indução explica por que o padrão nunca quebra. Caso base: com $n=1$, a soma é 1, que é $1^2$. Passo: suponha que os primeiros $k$ ímpares formam um quadrado de lado $k$. Para o seguinte, acrescente uma faixa vertical com $k$ peças, uma horizontal com outras $k$ e uma peça no canto — $2k+1$ peças, exatamente o próximo ímpar:

$$\underset{k^2}{\underbrace{1+3+\cdots +(2k-1)}}+(2k+1)=k^2+2k+1=(k+1{)}^2.$$

O poder não está em conferir uma imagem gigante: está em achar a operação que transforma uma imagem correta na próxima. A versão animada está na prova sem palavras.

Uma potência de novecentos dígitos

Agora um problema com cara de outra coisa: $8^n-1$ é sempre divisível por 7? Para $n=1$, 7. Para $n=2$, $63=7\times 9$. Para $n=3$, $511=7\times 73$. Mas tente $n=1000$: o número tem 904 dígitos. A lista infinita voltou, agora com contas impossíveis.

Então não calcule. Suponha que, para algum $k$, $8^k-1=7q$. Em vez de expandir o caso seguinte, reescreva-o:

$$8^{k+1}-1=8(8^k-1)+7=8\cdot 7q+7=7(8q+1).$$

O primeiro pedaço são oito cópias de um múltiplo de 7; o segundo é mais um 7. Nenhuma potência além da primeira foi calculada: a estrutura de um caso controlou o seguinte, e o tamanho do número virou irrelevante.

O tabuleiro com uma casa faltando

Pegue um tabuleiro de lado $2^n$ e arranque uma casa qualquer. O desafio: cobrir todo o resto com peças em forma de L, de três casas cada, sem sobrepor e sem sobrar buraco. No tabuleiro 2 × 2 é imediato — tira uma, sobram três, e três casas assim são exatamente um L. Esse é o caso base.

O pulo: corte um tabuleiro maior em quatro quadrantes. A casa arrancada está num deles; nos outros três não falta nada. Ponha uma peça em L no centro, ocupando uma casa de cada um dos três quadrantes cheios. Agora os quatro quadrantes têm a mesma descrição — um tabuleiro menor com exatamente uma casa faltando —, e se você sabe resolver o menor, resolveu os quatro. O 8 × 8 vira quatro 4 × 4; cada um vira quatro 2 × 2; e o 2 × 2 já está resolvido.

Repare no que essa prova entrega: não só que o ladrilhamento existe, mas o procedimento para construí-lo, qualquer que seja a casa arrancada. A hipótese indutiva virou ferramenta de construção. E de brinde vem uma conta: o número de peças é $(4^n-1)/3$, então $4^n-1$ tem de ser múltiplo de 3 — outra afirmação “para todo $n$”, provada sem conta.

Por que funciona de verdade

Dominó é uma analogia, e analogia não prova nada. Suponha então que a indução falhe: uma afirmação com caso base verdadeiro, passo válido, e que mesmo assim é falsa em algum lugar. Entre todos os números onde ela falha, existe um menor — um primeiro erro. Chame-o de $j$.

$j$ não pode ser 1, porque $P(1)$ é verdadeira. Então $j\ge 2$, e existe $j-1$. E $P(j-1)$ tem de ser verdadeira, porque $j$ era o primeiro erro. Mas o passo garante que $P(j-1)$ implica $P(j)$ — então $P(j)$ é verdadeira, e acabamos de dizer que era falsa. Contradição: o primeiro erro não existe. E sem primeiro erro, não existe erro nenhum.

Indução não é ver um padrão continuar e torcer para que ele continue. É achar a regra que torna impossível ele parar. Duas partes — começar e continuar —, simples o bastante para caber numa fileira de dominós, e poderosas o bastante para alcançar o infinito.

Os números do episódio

Desafios

Para ir além

• As provas sem palavras da série: a soma dos ímpares, a soma de Gauss, a soma dos cubos, cubos e ímpares e o tabuleiro.
• A indução lida com o infinito sem tocar nele — o próximo passo é tocar: o que é o infinito.
• No laboratório, o tabuleiro até 32 × 32.