Resumo Inducao

Prévia do material em texto

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) =      (hipótese de indução)
= k.(k + 1)/2 + (k + 1) =  (associatividade)
= (k + 1).(k/2 + 1) = 
= (k + 1)(k + 2)/2 = 
= (k + 1).[(k + 1) + 1]/2
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)³ =      (hipótese de indução)
= ( 1 + 2 +...+ k )² + ( k + 1 )³ =    (lema)
= [ k.( k + 1 ) / 2 ]² + ( k + 1 )³ = 
= k².( k + 1 )² / 2² + ( k + 1 )³ =    (associatividade)
= ( k + 1 )²/2².( k² + 2².k + 2² ) = 
= ( k + 1 )²/2².( k + 2 )² = 
= [( k + 1 ).( ( k + 1 ) + 1 ) / 2 ]² =    (lema)
= [ 1 + 2 +...+ k + ( k + 1 ) ]²
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) = (hipótese)
k² + (2(k + 1) – 1) =
k² + 2k + 1 =
(k + 1)²
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ãoverdadeiras;
  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
	Primeiro Princípio de Indução Matemática
	DEFINIÇÃO INDUTIVA
	Exemplo 5 - Múltiplos de 3