Indução Matemática!

Indução matemática é um método de prova matemática usado para demonstrar a verdade de um número infinito de proposições. A forma mais simples e mais comum de indução matemática prova que um enunciado vale para todos os números naturais n e consiste de dois passos:

1. A base: mostrar que o enunciado vale para n = 1
2. O passo indutivo: mostrar que, se o enunciado vale para n=k, então o mesmo enunciado vale para n=k+1.

Esse método funciona provando que o enunciado é verdadeiro para um valor inicial, e então provando que o processo usado para ir de um valor para o próximo é valido. Se ambas as coisas são provadas, então qualquer valor pode ser obtido através da repetição desse processo. Para entender por que os dois passos são suficientes, é útil pensar no efeito dominó: se você tem uma longa fila de dominós em pé e você puder assegurar que: O primeiro dominó cairá e sempre que um dominó cair, seu próximo vizinho também cairá, então você pode concluir que todos os dominós cairão.

Vamos ver um simples exemplo de uso do Princípio da Indução:

Prove por indução que a soma dos n primeiros números naturais é dada por S(n) = n(n+1)/2.

Temos: 

S(n) = 1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

1 - Para S(1) é verdadeiro, pois S(1) = 1(1+1)/2 = 1

2 - Supondo que S(n) é verdadeira, vamos desenvolver S(n+1):

S(n+1) = 1 + 2 + 3 + 4 + 5 + ... + n + (n+1)

Usando a hipótese de indução, vamos substituir o valor de S(n) na expressão acima.

Agora temos:

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

Colocando (n+1) em evidência teremos: 

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

Logo, S(n) = n(n+1)/2 é verdadeira para todo n natural.