A indução

Definição

A indução demonstra que uma propriedade $P(n)$P(n) vale para todo inteiro a partir de um índice $n_0$n0​, por meio de apenas duas verificações:

Esses dois pontos estabelecem infinitos enunciados. Aí está sua força: nunca se verifica mais que um caso e uma implicação.

Uma imagem, e seu limite

Uma fila de dominós: derrubar o primeiro, e garantir que cada um derrube o seguinte, basta para que todos caiam.

A imagem acerta no mecanismo e erra no alcance. Uma fila de dominós é finita e a queda leva tempo; a indução versa sobre infinitos índices e não se desenrola. Ela não narra uma propagação, prova uma propriedade.

Um exemplo levado até o fim

Mostremos que a soma dos $n$n primeiros inteiros vale $\dfrac{n(n+1)}{2}$2n(n+1)​.

Caso base. Para $n = 1$n=1: a soma vale 1, e $\dfrac{1 \times 2}{2} = 1$21×2​=1.

Passo indutivo. Suponhamos a fórmula verdadeira no índice $n$n. Então:

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

É a fórmula no índice $n+1$n+1. As duas etapas se sustentam, logo a propriedade vale para todo $n \geq 1$n≥1.

As duas etapas são necessárias

O passo indutivo sozinho nada prova. Tomemos $P(n)$P(n): «$n = n + 1$n=n+1».

Essa propriedade é hereditária: se $n = n+1$n=n+1, somando 1 aos dois lados obtém-se $n + 1 = n + 2$n+1=n+2. O passo se propaga perfeitamente — e a propriedade é falsa para todo inteiro, porque nenhum índice a inicia.

O caso base sozinho tampouco basta: uma propriedade pode ser verdadeira em 1 e falsa depois.

Indução forte

Certas demonstrações reclamam mais que o índice anterior. A indução forte supõe $P(k)$P(k) para todos os $k \leq n$k≤n, e não apenas para $n$n.

Serve quando o passo apela a um índice bem anterior — decompor um inteiro em fatores primos, por exemplo, remete a dois fatores menores quaisquer, não ao predecessor.

Resumo

Um ponto de partida e um passo que se propaga demonstram infinitos casos; nenhum dos dois é dispensável.