Indução Matemática

Indução é a técnica que permite provar infinitas afirmações com um argumento finito. Para quem programa, ela é a contraparte exata da recursão: provar por indução é escrever a versão em papel do mesmo raciocínio que justifica uma função recursiva.

O princípio

Para provar que $P(n)$ vale para todo $n \ge n_0$:

1. Base: mostre que $P(n_0)$ é verdadeiro.
2. Passo indutivo: mostre que, para todo $k \ge n_0$, se $P(k)$ vale então $P(k+1)$ vale.

A metáfora do dominó é boa: a base derruba a primeira peça, o passo garante que cada peça derruba a seguinte, e a conclusão é que todas caem.

A hipótese $P(k)$ usada no passo é a hipótese de indução. Ela não é o que se quer provar — é o que se pode supor para provar o caso seguinte.

Exemplo trabalhado

Provar que $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ para todo $n \ge 1$.

Base. Para $n = 1$: o lado esquerdo é $1$ e o direito é $\frac{1 \cdot 2}{2} = 1$. Vale.

Passo. Suponha $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$. Então:

$$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

$$= (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$$

que é exatamente a fórmula com $n = k+1$. Pelo princípio da indução, vale para todo $n \ge 1$. $\blacksquare$

Repare na mecânica: destacar o último termo, aplicar a hipótese ao resto e manipular até chegar à forma desejada. Esse é o roteiro da maioria das provas por indução sobre somas.

Indução forte

Às vezes $P(k)$ sozinho não basta e é preciso supor $P(n_0), P(n_0+1), \dots, P(k)$ — todos os casos anteriores. Essa variante é a indução forte, e é logicamente equivalente à simples.

Ela é a forma natural quando o passo recursivo não reduz o problema em uma unidade. Exemplo clássico: todo inteiro $n \ge 2$ tem fator primo. Se $n$ é primo, pronto. Se não, $n = ab$ com $2 \le a, b < n$, e a hipótese forte se aplica a $a$ — mas $a$ pode ser bem menor que $n-1$, então a indução simples não serviria.

O paralelo com algoritmos é direto: indução simples corresponde a recursão que decrementa em um; indução forte corresponde a dividir e conquistar, em que a chamada recursiva recebe um problema de tamanho arbitrariamente menor.

Indução estrutural

Generaliza a indução dos naturais para qualquer estrutura definida recursivamente — listas, árvores, fórmulas, expressões.

Para provar que uma propriedade vale para toda árvore binária:

1. Base: vale para a árvore vazia.
2. Passo: se vale para as subárvores esquerda e direita, vale para o nó que as combina.

Exemplo: provar que uma árvore binária com $n$ nós internos tem $n+1$ folhas.

• Base: árvore com $0$ nós internos é uma folha; $0 + 1 = 1$. Vale.
• Passo: um nó interno com subárvores de $n_1$ e $n_2$ nós internos tem $n_1 + n_2 + 1$ nós internos e, pela hipótese, $(n_1+1) + (n_2+1) = n_1 + n_2 + 2$ folhas — que é o número de nós internos mais um. Vale.

Indução estrutural é a ferramenta padrão para provar propriedades de linguagens de programação: preservação de tipos, correção de um avaliador, terminação de uma normalização.

Correção de algoritmos recursivos

A correspondência é exata:

Prova por indução	Algoritmo recursivo
Caso base	Caso base da recursão
Hipótese de indução	Confiar que a chamada recursiva funciona
Passo indutivo	Combinar os resultados corretamente
Boa fundamentação	Garantia de terminação

def soma(lista):
    if not lista:            # caso base
        return 0
    return lista[0] + soma(lista[1:])   # passo

Prova: para lista vazia devolve $0$, correto. Para lista de tamanho $k+1$, suponha que soma está correta em listas de tamanho $k$; então devolve o primeiro elemento mais a soma do resto, que é a soma total.

Este é o motivo pelo qual escrever uma função recursiva parece um ato de fé: você supõe que a chamada recursiva funciona, exatamente como a hipótese de indução. A fé é justificada desde que os argumentos decresçam segundo uma ordem bem fundada.

Invariantes de laço: indução disfarçada

Um laço se prova pelo mesmo mecanismo. O invariante é a propriedade $P$ que:

1. vale antes da primeira iteração (base),
2. é preservada por cada iteração (passo),
3. combinada com a negação da condição de parada, dá a pós-condição.

def maximo(v):
    m = v[0]
    for i in range(1, len(v)):
        # invariante: m == max(v[0..i-1])
        if v[i] > m:
            m = v[i]
    return m

O invariante é o que transforma "parece certo" em "está certo".

Erros comuns

• Esquecer o caso base. Sem ele nada se prova. O argumento "$n = n+1$ se $n-1 = n$" tem passo indutivo válido e nenhuma base.
• Provar a base errada. Se o enunciado é para $n \ge 2$, a base é $n = 2$.
• Usar a tese como hipótese. Supor $P(k+1)$ para provar $P(k+1)$ é circular.
• Aplicar indução simples onde é preciso a forte, especialmente em algoritmos de dividir e conquistar.
• Ignorar a boa fundamentação. Uma recursão cujos argumentos não decrescem numa ordem bem fundada pode não terminar, e a "prova" por indução não se aplica.

Leituras recomendadas

• Rosen, capítulo sobre indução e recursão — a apresentação mais didática e com mais exercícios resolvidos.
• Graham, Knuth e Patashnik, Concrete Mathematics, capítulo 1 — indução aplicada a problemas de contagem, com o problema da Torre de Hanói como fio condutor.
• Cormen et al., capítulo 2 — invariantes de laço aplicados à prova de correção do insertion sort.

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512. Ronald L. Graham and Donald E. Knuth and Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 9780134389967. Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058.

Referências

1. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
2. Ronald L. Graham; Donald E. Knuth; Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley.
3. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.