indução matematica

INDUÇÃO MATEMÁTICA
Indução Matemática é um método de prova matemática tipicamente usado para estabelecer que um dado enunciado é verdadeiro para todos os números naturais, ou então que é verdadeiro para todos os membros de uma seqüência infinita.
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 seguinte problema: Você está subindo uma escada infinitamente alta. Como saber que será capaz de chegar a um degrau arbitrariamente alto?
Suponha as seguintes hipóteses:
1. Você consegue alcançar o primeiro degrau;
2. Uma vez chegando a um degrau, você sempre é capaz de chegar ao próximo.
Pela hipótese 1, você é capaz de chegar ao primeiro degrau; pela hipótese 2, você consegue chegar ao segundo; novamente pela hipótese 2, chega ao terceiro degrau; e assim sucessivamente. Outra questão interessante de se pensar é o efeito dominó: se você tem uma longa fila de dominós em pé e você puder assegurar que:
1. O primeiro dominó cairá.
2. Sempre que um dominó cair, seu próximo vizinho também cairá. Então você pode concluir que todos os dominós cairão.
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 do seguinte:
1. Provamos que o número 0 tem a propriedade P: P(0);
2. Supomos que a propriedade P é válida pra qualquer número natural n: P(n);
3. Provamos que, se a propriedade P é válida para qualquer número natural n, então é válida para o próximo natural n+1: P(n)→P(n+1)
Primeiro Princípio de Indução Matemática
O Primeiro Princípio de Indução Matemática é formulado da seguinte forma:
1. P(0) é verdade;
2.