Prova por indução

[Enunciado]   Teorema: Para todo número natural n, vale a identidade 1 + 2 + ⋯ + n = n(n+1)/2.

Prova do teorema, por indução:

1. Para começar, tome n = 0. Nesse caso, a soma 1 + 2 + ⋯ + n é vazia e portanto vale 0 e a expressão n(n+1)/2 também vale 0. Portanto, a identidade que queremos provar vale quando n = 0. Esta é a base da indução.

2. Agora tome n > 0 e suponha que 1 + 2 + ⋯ + m = m(m+1)/2 para todo número natural m < n. Esta é a hipótese da indução.

3. A hipótese de indução vale, em particular, quando m = n − 1, uma vez que n ≥ 1. Logo,

1 + 2 + ⋯ + n = (1 + 2 + ⋯ + n−1)  +  n
  = (n−1)(n−1+1)/2  +  n
  = (n−1) n/2  +  n
  = ((n−1) n  +  2n)/2
  = (n−1 + 2) n/2
  = (n + 1) n/2 .

Esses cálculos constituem o passo da indução e mostram que 1 + 2 + ⋯ + n = n(n+1)/2, CQD.

Indução errada

Alguns novatos inexperientes fazem a prova por indução indo de n para n+1:

A. Quando n = 0, a identidade vale pois 1 + 2 + ⋯ + n = 0 e n(n+1)/2 = 0.

B. Agora suponha que a identidade vale para n e vamos provar que a identidade continua valendo se trocarmos n por n+1. Em outras palavras, vamos provar que 1 + 2 + ⋯ + n+1 = (n + 1)(n + 2) / 2.

C. Aqui está a prova:

1 + 2 + ⋯ + n + n+1 = (n + 1) n/2 + n+1
  = ((n + 1) n + 2(n+1)) / 2
  = (n + 1)(n + 2) / 2 .

Há quem diga, em tom de piada, que uma prova desse tipo é uma indução mirim, ou indução infantil.

Essa prova está ERRADA porque confunde a tese com a hipótese. No passo B, a prova supõe que a identidade 1 + 2 + ⋯ + n = n(n+1)/2 vale. Ora, não faz sentido supor algo que deveríamos provar.

Algoritmos

O teorema tem implicações algorítmicas interessantes. Os dois lados da identidade representam o mesmo número. O lado esquerdo, representa uma maneira ineficiente de calcular esse número:

Ineficiente (n)
1 . se n = 0
2 .ooo devolva 0 e pare
3 . devolva Ineficiente (n − 1) + n

O lado direito representa um algoritmo bem mais eficiente:

Eficiente (n)
1 . devolva n(n + 1)/2