[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.
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.
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 |