Indução matemática

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:

1. A base: mostrar que o enunciado vale para n = 0, ou n = 1, dependendo da definição utilizada de $\mathbb {N}$;
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 proposições 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:

1. O primeiro dominó cairá.
2. Sempre que um dominó cair, seu próximo vizinho também cairá.

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

Indução matemática versus indução empírica (nas ciências naturais)

Nas ciências naturais, utiliza-se a indução empírica. Ou seja, a partir de um grande número de observações particulares selecionadas adequadamente, formulam-se leis que devem reger determinados fenômenos. A validade de um teorema matemático, no entanto, se estabelece de forma completamente diferente. Verificar que certa afirmação vale para um grande número de casos particulares (como se faz nas ciências naturais) não permitirá concluir que esta afirmação é válida (como é notado no Teorema das quatro cores, por exemplo). O princípio da indução completa (ou método da recorrência) é utilizado para provar que a proposição vale para todos os casos (ou seja, na verdade há uma proposição para cada caso, frequentemente um número infinito de casos).

Exemplo

Suponha que desejemos provar o seguinte enunciado:

$5+10+15+...+5n={\frac {5n(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.

Verificação pelo princípio da indução finita

O primeiro passo consiste em determinar a base da prova por indução. Neste caso, tomaremos como base n = 1. Claramente, do lado esquerdo da equação fica 5 e do lado direito 5*1(1 + 1) / 2, resolvendo dá 5=5 =>1=1. Então o enunciado é verdadeiro para n = 1.

Agora precisamos provar que o enunciado vale para n = k.

Dividindo os dois lados do enunciado por 5 temos:

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

(Provar esta igualdade é equivalente a provar o enunciado proposto. Podemos verificar para n=1 que 1 = 1*(1+1)/2 => 1 = 1.)

Por hipótese de indução, a equação vale para n = k-1, ou seja:

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

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

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

Por manipulação algébrica, temos:

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

Logo:

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

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

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

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

1. Primeiro provamos que a base de indução (n=1, neste caso) é verdadeira;
2. Depois, por hipótese de indução temos que P(k-1) é verdadeiro, então precisamos provar que P(k) também é verdadeiro.
3. Provando que o passo da indução está correto, concluímos que P(n) é verdadeiro para qualquer número n natural.

Generalizações

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:

1. Mostrar que o enunciado vale quando n = b;
2. 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.

Assumir verdadeiro para todos os valores menores

Outra generalização, chamada indução completa, permite que no segundo passo nós não apenas assumimos 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 surpreendentemente, 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 de Proporção áurea). 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:

1. deixar P(n) ser o enunciado que pretendemos provar,
2. 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.

Indução transfinita

Ver artigo principal: Indução transfinita

Os últimos dois passos podem ser reformulados em um:

1. 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:

1. k é um elemento mínimo, ou seja, não há elemento menor que k
2. k tem um predecessor direto, ou seja, o conjunto de elementos que são menores que k tem um elemento maior
3. 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 contraexemplos.

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, se adicionada a hipótese que nenhum numero antecede o menor natural ( veja Axiomas de Peano e o "Um modelo diferente dos números Naturais" ). Isto é, os dois são equivalentes.

Ver também

• Princípio da boa-ordenação