Indução matemática

Origem: Wikipédia, a enciclopédia livre.

Atenção: Esta página foi marcada para revisão!
Se tem algum conhecimento sobre este assunto, por favor verifique a consistência e o rigor deste artigo.

O efeito dominó.

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:

A base: mostrar que o enunciado vale para n = 1.
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á.
Sempre que um dominó cair, seu próximo vizinho também cairá.

então você pode concluir que todos os dominós cairão.

Índice

1 Exemplo
- 1.1 Demonstração
2 Generalizações
3 Prova ou reformulação da indução matemática
4 Ver também

[editar] Exemplo

Suponha que desejemos provar o seguinte enunciado:

$1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}$

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.

[editar] 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 o enunciado é válido para n = k, ou seja:

$1 + 2 + ... + k = \frac{k(k + 1)}{2}$

Adicionando k + 1 a ambos os lados:

$1 + 2 + ... + k + (k + 1) = \frac{k(k + 1)}{2} + (k+ 1)$

Por manipulação algébrica, temos:

$= \frac{k(k + 1)}{2} + \frac{2(k + 1)}{2} = \frac{(k + 2)(k + 1)}{2}$

Logo:

$1 + 2 + ... + (k + 1) = \frac{(k + 1)((k + 1) + 1)}{2}$

Este último é o enunciado para n = k + 1. Note que ele não foi provado como verdadeiro: nos assumimos que P(k) é verdadeiro, e desta assunção concluímos que P(k + 1) é verdadeiro. Simbolicamente, mostramos que:

$P(k) \Rightarrow P(k + 1)$

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

P(1) é verdadeiro, logo P(2) é verdadeiro (usando o passo indutivo)
Como P(2) é verdadeiro, então P(3) também é
Então usando-se o passo indutivo P(N) será verdadeiro e o P(N+1) também

[editar] Generalizações

[editar] Comece em b

Este tipo de prova pode ser generalizada de várias maneiras. Por exemplo, se quisermos provar um enunciado, não para todos os números naturais, mas apenas para todos os números maiores que ou iguais a um determinado número b, então os seguintes passos são suficientes:

Mostrar que o enunciado vale quando n = b.
Mostrar que se o enunciado vale para n = k ≥ b, então o mesmo enunciado também vale para n = k + 1.

Isto pode ser usado, por exemplo, para mostrar que n² > 2n para n ≥ 3. Esta forma de indução matemática é na verdade um caso especial da forma anterior, porque se o enunciado que pretendemos provar é P(n), então prová-lo com estas duas regras é equivalente a provar P(n + b) para todos os números naturais n com os dois primeiros passos.

[editar] Assumir verdadeiro para todos os valores menores

Outra generalização, chamada indução completa, permite que no segundo passo nós não apenas assumamos que o enunciado vale para n = k, mas também para todo n menor que ou igual a k.

Nesta forma de indução, talvez supreendentemente, não é necessário provar que a proposição é verdadeira no primeiro caso. Isto se dá porque a proposição vale para todos os casos antes do primeiro caso, simplesmente porque não há casos antes do primeiro.

Isto pode ser usado, por exemplo, para mostrar que

$\operatorname{fib}(n) = \frac{ \varphi^n - (-1/\varphi)^n }{\sqrt{5}}$

onde fib(n) é o enésimo número de Fibonacci e Φ = (1 + √5)/2 (também chamado meio dourado). Dado que fib(k + 1) = fib(k) + fib(k - 1), pode-se provar que o enunciado vale para m + 1 se pudermos assumir que ele também vale tanto para k quanto para k - 1. (Por isso a prova desta identidade requer uma base dupla — requer inicialmente a demonstração de que a identidade é verdadeira tanto para n = 0 quanto para n = 1). Esta generalização é apenas um caso especial da primeira forma:

deixar P(n) ser o enunciado que pretendemos provar,
então prová-lo com estas duas regras é equivalente a provar o enunciado "P(k) para todo k ≤ n" para todo número natural n com os dois primeiros passos.

[editar] Indução Transfinita

Artigo principal: Indução transfinita

Os últimos dois passos podem ser reformulados em um:

Mostrar que se o enunciado vale para todo n < k, então o mesmo enunciado também vale para n = k.

Este é, na verdade, a forma mais geral de indução matemática, e pode-se mostrar que esta não vale apenas para enunciados sobre números naturais, mas também para enunciados sobre elementos de qualquer conjunto bem fundado, ou seja, um conjunto com ordem parcial que não contém correntes decrescentes infinitas (onde < é definido tal que a < b sse a ≤ b e a ≠ b).

Esta forma de indução, quando aplicada a ordinais (que formam uma classe bem ordenada e, por isso, bem fundada), é chamada indução transfinita. É uma importante técnica de prova na teoria dos conjuntos, na topologia e em outras áreas.

Provas por indução transfinita geralmente precisam distinguir três casos:

k é um elemento mínimo, ou seja, não há elemento menor que k
k tem um predecessor direto, ou seja, o conjunto de elementos que são menores que k tem um elemento maior
k não tem um predecessor direto, ou seja, k é chamado de ordinal limite.

A rigor, não é necessário provar a base na indução transfinita, porque este é um caso especial vazio da proposição de que se P é verdadeiro para todo n < k, então P é verdadeiro para k. Isto é precisamente verdadeiro, porque não há valores para n < k que poderiam servir como contra-exemplos.

[editar] Prova ou reformulação da indução matemática

O princípio da indução matemática é geralmente tido como um axioma de números naturais (ver Axiomas de Peano). Porém, ele pode ser provado em alguns sistemas lógicos. Por exemplo, se o seguinte axioma (chamado de princípio da boa-ordenação para números naturais) é empregado:

O conjunto de números naturais é bem ordenado

O axioma adicional é certamente uma formulação alternativa do princípio da indução matemática. Isto é, os dois são equivalentes.