Princípio de Indução

Suponhamos que para cada n≥a está dada uma afirmação A(n) de forma que:

i) A(a) é verdadeira.

ii) Se A(a) é verdadeira para todo  inteiro m tal que a≤m≤k então A(k+1) é verdadeira.

Então A(n) é verdadeira para todo inteiro n≥a.

Demonstração:

Dado um conjunto S com todos os inteiros maiores ou iguais a a. Afirmamos que 1+2+..+n = n(n+1)/2

Verificando para n=1

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

Assim, a afirmação de que a somatória de todos elementos de 1 a n dada por  n(n+1)/2, é válida  para n=1. Queremos provar que a afirmação também é válida para n=k+1.

 Estamos admitindo que  1+2+...+k = k(k+1)/2

Vamos somar k+1 de ambos os lados

1+2+...+k+(k+1)=k(k+1)/2+(k+1)

                          = [k(k+1)+2(k+1)]/2

                          = (k+1)(k+2)/2

                          =(k+1)((k+1)+1)/2

Que é a fórmula correspondente a n=k+1, como queríamos demonstrar.