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.
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).
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.
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 = n ( n + 1 ) 2 {\displaystyle 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: Adicionando k a ambos os lados, a igualdade se mantém, então:
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: 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 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:
Indução transfinita
Os últimos dois passos podem ser reformulados em um: 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:
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 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.
