Indução matemática

Para provar, por indução matemática, que uma certa afirmação ou proposição P(n) vale para todo número natural n, siga a seguinte receita:

1. Base da indução: verifique P(0), P(1), … , P(k−1) diretamente para algum k ≥ 1.
2. Hipótese de indução: suponha que P(0), P(1), … , P(n−1) valem para algum n ≥ k.
3. Passo da indução: deduza P(n) de P(0), P(1), … , P(n−1).

(Essa receita é essencialmente a mesma da recursão.)  Às vezes é preciso começar a indução a partir de um número natural i maior que 0. A receita fica assim:

1. Base da indução: verifique P(i), P(i+1), … , P(k−1) diretamente para algum k ≥ i+1.
2. Hipótese de indução: suponha que P(i), P(i+1), … , P(n−1) valem para algum n ≥ k.
3. Passo da indução: deduza P(n) de P(i), P(i+1), … , P(n−1).

No passo 3, às vezes é possível deduzir P(n) de P(n−1) apenas, igorando P(i), … , P(n−2).  Outras vezes (como na análise da divisão e conquista), deduzimos P(n) de P(⌊n/2⌋), igorando todas as demais proposições da sequência P(i), P(i+1), … , P(n−1). É claro que nesse caso é preciso certificar-se de que i ≤ n/2, ou seja, de que k ≥ 2i.

(Veja exercícios no Apêndice.)

Indução errada. Alguns novatos fazem a prova por indução indo de n para n+1. Mais precisamente, trocam o passo 2 por

suponha que P(i), P(i+1), … , P(n−1), P(n) valem para algum n ≥ k−1

e o passo 3 por

deduza P(n+1) de P(i), P(i+1), … , P(n).

Isso não é bom porque confunde a tese com a hipótese: no passo 2, a prova supõe que P(n) vale. Ora, não faz sentido supor algo que deveríamos provar. Há quem diga, em tom de piada, que esse tipo de indução é uma indução mirim, ou indução infantil. Os defeitos dessa organização da indução ficam especialmente aparentes quando o movimento de n para n+1 precisa ser substituído pelo movimento de n para 2n e 2n+1.