Exercícios Resolvidos de Princípio da Indução Finita

Ver Teoria

Enunciado

Seja a 0 = 1 e, para n > 0 , seja a n = 2 a n - 1 + 1 . Os primeiros termos da sequência a 0 ,   a 1 ,   a 2 ,   a 3 ,   … são 1 ,   3 ,   7 ,   15 ,   …

Quais são os próximos dois termos?

Prove que a n = 2 n + 1 - 1

Passo 1

FAAAAALA MEU AMOR!!! Bora começar do começo!

Para dizermos quais são os próximos dois termos, NÃO podemos usar a fórmula que foi dada! (Aí seria muito molezinha né meu anjo!)

Então, já temos todos os termos até o a 3 , vamos em busca dos outros:

a 4 = 2 a 3 + 1 = 2.15 + 1 = 31

a 5 = 2 a 4 + 1 = 2.31 + 1 = 63

Passo 2

Bora, fazer o segundo passo, que é provar que a fórmula é verdade! Vamos usar o PIF versão 1 :

Lembrando que no nosso caso, P n = 2 n + 1 - 1

Vamos atacar a primeira condição, onde chamarei n 0 = 0

a 0 = 1

P 0 = 2 0 + 1 - 1 = 1

Show! P ( 0 ) é verdadeira!!!

Passo 3

Vamos atacar a segunda condição. Usando a hipótese indutiva de que P ( k ) é válida, temos:

a k = 2 k + 1 - 1

Queremos que P ( k + 1 ) seja verdadeira, então vamos usar a outra relação:

a k + 1 = 2 a k + 1

Mas, como k obedece a fórmula, podemos substituir:

a k + 1 = 2 2 k + 1 - 1 + 1

a k + 1 = 2 k + 2 - 1

Olha que lindo!!! P ( k + 1 ) é verdadeira! Lembrando que:

P k + 1 = 2 k + 2 - 1

Portanto, P ( n ) é verdadeira para todo n ≥ 0 .

Resposta

a 4 = 31

a 5 = 63

Demonstração por PIF versão 1 .