Indução Matemática

A indução matemática a primeira olhada parece ser coisa de outro mundo, mas não bem assim ela e "bem interessante" mas não e nada impossivel de ser resolvida.
Vejamos um exemplo;

Suponha que desejemos provar o seguinte enunciado:

para todos os números naturais n. Esta é uma fórmula simples para a soma dos números naturais de 1 a n. A prova de que o enunciado é verdadeiro para todos os números naturais n é dada a seguir.

Demonstração

Verificar se o enunciado é verdadeiro para n = 1. Claramente, do lado esquerdo da equação fica 1 e do lado direito 1(1 + 1) / 2, resolvendo dá 1=1. Então o enunciado é verdadeiro para n = 1. Podemos definir este enunciado como P(n) e portanto temos que P(1) é verdadeiro.

Agora precisamos mostrar que se o enunciado vale quando n = k, então ele também vale quando n = k + 1. Isto pode ser feito da seguinte maneira:

Assuma que a seguinte igualdade é válida para para n = k, ou seja:

Adicionando k + 1 a ambos os lados, a igualdade se mantém, então:

Por manipulação algébrica, temos:

Logo:

Este último é o enunciado para n = k + 1. Note que, assumindo que P(K) é verdadeiro, podemos concluir que P(K + 1) é verdadeiro. Simbolicamente, mostramos que:

Por indução, no entanto, podemos concluir que o enunciado P(n) vale para todos os números naturais n:

1. Primeiro provamos que P(1) é verdadeiro;
2. Depois provamos que se P(k) é verdadeiro, então P(k+1) também é verdadeiro.
3. Sabendo que P(1) é verdadeiro, concluimos que P(2) é verdadeiro e pelo passo de indução sabemos que P(n) é verdadeiro para qualquer número n natural.

no entanto apos essa pequena demonstração da para ter uma noção de que não e tão complicado a "dita" Indução Matemática.