Princípio da Indução Matemática
e Recursividade
Indução Matemática é um processo de prova ou demonstração de propriedades definidas
sobre o conjunto dos números inteiros que, baseada numa quantidade finita de observações,
estende
e generaliza a propriedade para todo o conjunto de números inteiros.
O processo de prova baseia-se nos seguintes argumentos:
Prove que a propriedade vale para
n=1, supondo que a propriedade vale para n,
prove que
ela também vale para n+1.
Elaine Teixeira de Oliveira
Princípio de Indução Matemática
Lembrete:
Para provar que alguma
coisa é verdadeira para
todo inteiro n  que
algum valor, pense em
indução.
Para provar n  N P(n):
Provar:
1. P(0)
(caso base)
2. (k)[P(k)  P(k+1)] (passo indutivo)
Demonstrações por Indução Matemática
Árvore genealógica da família Silva
Geração
1
Descendentes
2 = 21
2
4 = 22
3
8 = 23
.
.
.
.
.
.
.
.
.
Parece que a geração n contém
2n
descendentes. Mais formalmente, P(n) = 2n.
Princípio de Indução Matemática
Exemplo 6.4:
20 = 1 = 21 – 1
20 + 21 = 1 + 2 = 3 = 22 – 1
20 + 21 + 22 = 1 + 2 + 4 = 7 = 23 – 1
20 + 21 + 22 + 23 = 1 + 2 + 4 + 8 = 15 = 24 – 1
No exemplo acima o padrão mais geral parece com:
20 + 21 + 22 +…+ 2n = 2n-1 – 1
Mas, não podemos afirmar que este padrão será sempre
verdadeiro para todos os valores de n a menos que
provemos.
Prove que para todo número natural n, 20 + 21 + 22
+…+ 2n = 2n-1 – 1.
Princípio de Indução Matemática
1. Prove que n  N, 3|(n3 – n), ou seja, que n3 – n é
divisível por 3.
2. Prove que n  5, 2n > n2.
3. Prove que para todo inteiro positivo n, n2> n
4. Prove que n2 > 3n para n  4.
5. Prove que o número 22n – 1, n  N é divisível por 3.
6. 12 + 22 + … + n2 = k(k+1)(2k+1)/6
7. 1+3+5 +...+ (2n-1) = n2.
Relações de Recorrência
Definições recorrentes
Uma definição onde o item sendo definido aparece como
parte da definição é chamada de definição recorrente
ou definição por recorrência ou ainda definição por
indução.
Como??
1. Uma base, ou condição básica, onde alguns casos
simples (pelo menos um) do item que está sendo
definido são dados explicitamente.
2. Um passo de indução ou recorrência, onde novos
casos do item que está sendo definido são dados em
função dos casos anteriores.
Seqüências Definidas por Recorrência
Define-se o primeiro valor (ou alguns poucos ) na
seqüência e depois os valores subseqüentes na
seqüência em termos de valores anteriores
Exemplo:
A seqüência S é definida por recorrência por
1. S(1) = 2
Relação de
2. S(n) = 2S(n -1) para n  2
Recorrência
Algoritmos Definidos por Recorrência
S(inteiro n)
//função que calcula iterativamente o valor S(n) para a seqüência S do exemplo
//anterior
Variáveis locais:
inteiro i
//índice do laço
Valor corrente // valor corrente da função S
Algoritmo
se n = 1 então
Iterativo
retorne 2
senão
i=2
ValorCorrente = 2
enquanto i <= n faça
ValorCorrente = 2 * ValorCorrente
i=i+1
fim do enquanto
//agora o ValorCorrente tem o valor S(n)
retorne ValorCorrente
fim do se
fim da função S
Algoritmos Definidos por Recorrência
S(inteiro n)
//função que calcula o valor S(n) de forma recorrente para a
//seqüência S do exemplo anterior
se n = 1 então
retorne 2
Algoritmo
senão
retorne 2 * S(n - 1)
Recorrente
fim do se
fim da função S
Mais curto
Mais complicado
Pode acontecer overflow
Resolvendo relações de recorrência
Lembrando, do exemplo anterior:
S(1) = 2
(1)
S(n) = 2S(n - 1) para n  2
(2)
Como
Solução em
S(1) = 2 = 21
forma fechada
2
S(2) = 4 = 2
para a relação de
recorrência (2)
S(3) = 8 = 23
sujeita à condição
básica (1)
S(4) = 16 = 24
e assim por diante, vemos que
S(n) = 2n
(3)
É possível calcular diretamente S(n) sem ter que calcular
explicitamente ou por recorrência.
Problemas Recorrentes
Problemas onde soluções utilizam a idéia de
recorrência, onde a solução de cada problema
depende de soluções de casos mais simples do
mesmo problema.
A Torre de Hanói
 Matemático francês Édouard Lucas
em 1883 (8 discos).
 Lenda romântica sobre a Torre de
Brama, com 64 discos de ouro
empilhados em três agulhas de
diamantes.
Problemas Recorrentes – Torre de Hanói
Considerando uma torre com n discos
1. n – 1 discos menores para pino intermediário (Tn-1 movimentos)
2. maior disco (um movimento)
3. n – 1 discos menores em cima do maior (Tn-1 movimentos)
Tn  2Tn + 1, para n > 0
Corremos o risco de mover o maior disco mais de uma vez
Tn  2Tn + 1, para n > 0
Essas duas inequações junto com a trivial para n = 0, fornecem
T0 = 0
Tn = 2Tn-1 + 1, para n > 0
Como resolver essa relação de recorrência?
Problemas Recorrentes – Torre de Hanói
Uma possibilidade é adivinhar a solução e depois provar que
adivinhamos corretamente. (Casos mais simples)
T1 = 2 * 0 + 1 = 1
T2 = 2 * 1 + 1 = 3
T3 = 2 * 3 + 1 = 7
T4 = 2 * 7 + 1 = 15
T5 = 2 * 15 + 1 = 31
T6 = 2 * 31 + 1 = 63
Está parecendo que
Tn = 2n – 1
Vamos provar!
Problemas Recorrentes – Torre de Hanói
Dicas para encontrar uma forma fechada, ou seja, encontrar
uma solução da relação de recorrência:
1. Considere casos simples. Isso nos faz compreender
melhor o problema e nos ajuda nas etapas 2 e 3.
2. Ache uma expressão matemática e prove sua validade.
3. Ache uma forma fechada para a expressão matemática
e demonstre sua validade.
Curiosidade:
Para a Torre de Brama (n=64), serão necessários 264 –1 movimentos
(aproximadamente 18 quintilhões). Com a velocidade de um movimento
por microssegundo, isso levaria 5000 séculos!
Exercícios
Prove que
1. 1 + 2 + 22 + … + 2n = 2n+1 - 1, para todo n  1.
2. Para qualquer inteiro positivo n, 2n > n.
3. Para todo inteiro positivo n, o número 22n – 1 é
divisível por 3.
4. Prove 13 + 23 + … + n3 = 1/4(n+1)2 n2
5. Encontre uma solução em forma fechada para a
relação de recorrência
S(n) = 2S(n-1) + 3 para n  2
sujeita à condição básica
S(1) = 4