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. (∀ k)(P(k) é verdade →P(k+1) é verdade).
Com isto, provamos que a propriedade é verdadeira para todo o natural n, ou seja, que P(n) é verdade.
A tabela abaixo, resume os três passos necessários para uma demonstração que usa o primeiro princípio de indução:
Demonstração por Indução
Passo 1
Prove a base de indução
Passo 2
Suponha P(k)
Passo 3
Prove P(k+1)
Exemplo 1 ­ Prova formal por indução da seguinte equivalência:
1³ + 2³ +...+ n³ = (1 + 2 +...+ n)²
Na prova da igualdade acima, utilizaremos um lema, que diz que a soma de n números naturais vale n.(n + 1)/2, ou seja:
1 + 2 + ... + n = n.(n + 1)/2
Provaremos esse lema também por indução.
Prova formal do lema:
•
Base de indução:
Para n = 0, temos que 0 = 0.1/2 = 0, então temos uma base verdadeira.
•
Hipótese de indução:
Suponhamos que, para um k qualquer, valha que 1 + 2 + ... + k = k.(k + 1)/2
•
Passo de Indução:
Para o sucessor de k, ou seja, para k + 1, desejamos provar que:
1 + 2 + ... + k + (k+1) = (k + 1).[(k + 1) + 1]/2
Partimos de que:
1 + 2 + ... + k + (k+1) = = k.(k + 1)/2 + (k + 1) = = (k + 1).(k/2 + 1) = = (k + 1)(k + 2)/2 = = (k + 1).[(k + 1) + 1]/2
(hipótese de indução)
(associatividade)
Logo, conseguimos provar o que queríamos, pois supondo que a igualdade vale para k, prova­se que ela vale para k + 1, e como temos uma base, a igualdade vale para a base e para todos os seus sucessores. Então, para todos os números naturais, a igualdade é válida. Formalizando:
1 + 2 + ... + k = k.(k + 1)/2 → 1 + 2 + ... + k + (k+1) = (k + 1).[(k + 1) + 1]/2
Agora, podemos usar este lema na prova da igualdade que desejamos provar.
Prova formal da igualdade da soma de n cubos de números é igual o quadrado da soma dos n números:
•
Base de indução
:
Para n = 0, temos que 0³ = 0 = 0², pois não somamos nenhum termo em ambos os lados.
•
Hipótese de Indução
:
Suponhamos que, para um k qualquer, valha que 1³ + 2³ +...+ k³ = (1 + 2 +...+ k)²
•
Passo de Indução
:
Para o sucessor de k, ou seja, para k + 1, desejamos provar que:
1³ + 2³ +...+ k³ + (k + 1)³ = [1 + 2 +...+ k + (k + 1)]²
Partimos de que:
1³ + 2³ +...+ k³ + (k + 1)³ = = ( 1 + 2 +...+ k )² + ( k + 1 )³ = = [ k.( k + 1 ) / 2 ]² + ( k + 1 )³ = = k².( k + 1 )² / 2² + ( k + 1 )³ = = ( k + 1 )²/2².( k² + 2².k + 2² ) = = ( k + 1 )²/2².( k + 2 )² = = [( k + 1 ).( ( k + 1 ) + 1 ) / 2 ]² = = [ 1 + 2 +...+ k + ( k + 1 ) ]²
(hipótese de indução)
(lema)
(associatividade)
(lema)
Logo, conseguimos provar o que queríamos, pois supondo que a igualdade vale para k, prova­se que ela vale para k + 1, e como temos uma base, a igualdade vale para a base e para todos os seus sucessores. Então, para todos os números naturais, a igualdade é válida. Formalizando:
1³ + 2³ + ... + k³ = ( 1 + 2 +...+ k )² → 1³ + 2³ +...+ k³ + (k + 1)³ = [1 + 2 +...+ k + (k + 1)]²
Exemplo 2 ­ Prova formal por indução da seguinte desigualdade:
n² > 2n , ∀n ≥ 3
Na prova da desigualdade acima, utilizaremos um lema, que diz que a soma de 2n ­ 1 números ímpares vale n², ou seja:
1 + 3 + ... + (2n – 1) = n²
Provaremos esse lema também por indução.
Prova formal do lema:
•
Base de indução:
Para n = 1, temos que 1 = 1² = 1, então temos uma base verdadeira.
•
Hipótese de indução:
Suponhamos que, para um k qualquer, valha que 1 + 3 + ... + (2k – 1) = k²
•
Passo de Indução:
Para o sucessor de k, ou seja, para k + 1, desejamos provar que:
1 + 3 + ... + (2k – 1) + (2(k + 1) – 1) = (k + 1)²
Partimos de que:
1 + 3 + ... + (2k – 1) + (2(k + 1) – 1) =
k² + (2(k + 1) – 1) =
k² + 2k + 1 =
(k + 1)²
(hipótese)
Logo, conseguimos provar o que queríamos, pois supondo que a igualdade vale para k, prova­se que ela vale para k + 1, e como temos uma base, a igualdade vale para a base e para todos os seus sucessores. Então, para todos os números naturais a partir de 1, a igualdade é válida. Formalizando:
1 + 3 + ... + (2k – 1) = k² → 1 + 3 + ... + (2k – 1) + (2(k + 1) – 1) = (k + 1)²
Agora, podemos usar este lema na prova da desigualdade que desejamos provar.
Prova formal da desigualdade do quadrado de um número é maior que seu dobro:
•
Base de indução
:
Para n = 3, temos que 3² = 9 > 6 = 2.3.
•
Hipótese de Indução
:
Suponhamos que, para um k qualquer, valha que k² > 2k
•
Passo de Indução
:
Para o sucessor de k, ou seja, para k + 1, desejamos provar que:
(k + 1)² > 2(k + 1)
Partimos de que:
(k + 1)² = k² + 2k + 1 =
(lema)
1 + 3 + ... + (2k – 1) + 2k + 1 = (comutatividade)
2k + 1 + 1 + 3 + ... + (2k – 1) = (2k + 2) + 3 + ... + (2k ­1) > 2k + 2 = 2(k + 1)
Logo, conseguimos provar o que queríamos, pois supondo que a desigualdade vale para k, prova­se que ela vale para k + 1, e como temos uma base, a igualdade vale para a base e para todos os seus sucessores. Então, para todos os números naturais maiores ou iguais a 3, a desigualdade é válida. Formalizando:
k² > 2k → (k + 1)² > 2(k + 1)
SEGUNDO PRINCÍPIO DA INDUÇÃO MATEMÁTICA
Normalmente denominada indução forte, essa formulação do princípio da indução matemática (o Segundo Princípio da Indução Matemática.) é geralmente utilizado na definição e na prova de propriedades de expressões, fórmulas, árvores, etc., razão pela qual esse princípio freqüentemente é denominado também de indução em estrutura, indução estruturada, ou ainda, indução estrutural.
Definição: Seja p(n) uma proposição sobre M = {n ∈ N | n ≥ m, m ∈ N}. O Segundo Princípio da Indução Matemática pode, equivalentemente, ser definido como segue:
a) Primeira Versão
a.1) p(m) é verdadeira;
a.2) Para qualquer k ∈ M, vale:
p(m) ∧ p(m+1) ∧ ... ∧ p(k) ⇒ p(k+1)
a.3) Então, para qualquer n ∈ N, p(n) é verdadeira.
b) Segunda Versão. Suponha t ∈ N:
b.1) p(m), p(m+1), ..., p(m+t), são verdadeiras;
b.2) Para qualqur k ∈ M tal que k ≥ m+t, vale:
p(m) ∧ p(m+1) ∧ ... ∧ p(k) ⇒ p(k+1)
b.3) Então, para qualquer n ∈ N, p(n) é verdadeira.
Note que a segunda versão do Segundo Princípio da Indução Matemática tem t casos separados na sua base, ao invés de somente o primeiro.
Exemplo 3 ­ Prova formal da fatoração em números primos:
Desejamos provar por indução a seguinte afirmativa:
Qualquer número natural maior que 1 é primo ou um produto de primos.
Prova:
m = 2
M = {2,3,4,...}
• Base de Indução
:
2 é primo.
•
Hipótese
de Indução
: p(2) é verdade ∧ p(3) é verdade ∧ p(4) é verdade ∧ ... ∧ p(k) é verdade
•
Passo de Indução
:
(mostrar p(k+1) supondo p(2), p(3), p(4), ..., p(k))
2 possibilidades:
1) k+1 é primo.
Como k+1 é primo, p(k+1) é verdade.
2) k+1 é composto.
k+1 =
a . b , 1<a<k+1, 1<b<k+1, a,b ∈ N = hipótese
p(a) é verdade ∧ p(b) é verdade =
p(a . b) é verdade =
p(k+1) é verdade.
Logo, a proposição é verdadeira e foi demonstrada pelo princípio da indução forte.
Exemplo 4 ­ Fatoração de números como produtos de 4 e 5:
(∀n ∈ N)(n ≥ 12 → n = 4.a + 5.b)
Prova:
m = 12
M = {12, 13, 14, ...}
•
Base de Indução
:
12 = 3.4 + 0.5
13 = 2.4 + 1.5
14 = 1.4 + 2.5
15 = 0.4 + 3.5
•
Hipótese de Indução
:
p(12) é V ∧ p(13) é V ∧ p(14) é V ∧ ... ∧ p(k) é V
•
Passo de Indução
:
(mostrar que p(k+1) é V, supondo p(12), p(13), ..., p(k))
k+1 = (k­3 + 3) + 1 = k­3 + 4 = subs k­3 por u
u + 4 = p(u) é V (pela hipótese)
p(u+4) é V =
p(k­3+4) é V =
p(k+1) é V.
Logo, a proposição é verdadeira e foi demonstrada pelo princípio da indução forte.
DEFINIÇÃO INDUTIVA
O Princípio da Indução Matemática pode ser usado também em definições. Uma definição de uma construção usando esse princípio é denominada definição indutiva ou definição recursiva. Nesse caso, afirma­se que a construção é indutivamente definida ou recursivamente definida. Esse tipo de definição é particularmente útil para definir conjuntos (normalmente infinitos) que seguem uma certa regra para seus elementos.
Resumidamente, em uma definição indutiva:
• a base de indução mostra os casos elementares;
• o passo de indução determina como os demais casos são definidos em termos dos anteriores (em se tratando de conjuntos, dita uma regra para que um elemento pertença ao conjunto).
Exemplo 5 ­ Múltiplos de 3
M = {..., ­6, ­3, 0, 3, 6, ...}
1) 3 ∈ M
2) x ∈ M → x.k ∈ M, k ∈ Z
3) Nada mais pertence ao conjunto M.
Exemplo 6 ­ Polinômios
P = Conjunto dos Polinômios em x com coeficientes reais e expoentes naturais
1) 0 ∈ P
1 ∈ P
x ∈ P
2) y ∈ P → y + axb ∈ P, a ∈ R, b ∈ N
3) Nada mais pertence ao conjunto P
Exemplo 7 ­ Linguagem com o dobro de "a" que de "b"
P = Conjunto das palavras sobre {a,b} cuja quantidade de “a” é o dobro da quantidade de “b”
1) ε ∈ P
2) x ∈ P → xaab, xaba, xbaa, axab, axba, bxaa, aaxb, abxa, baxa, aabx, abax, baax
3) Nada mais pertence ao conjunto P