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

Ver Teoria

Enunciado

Numa certa criação de coelhos o número de coelhos a n após n meses obedece a seguinte regra:

a n = 3 a n - 1 - 2 a n - 2

Sabe-se também que a 1 = 3 e a 2 = 7 . Mostre que:

a n = 2 n + 1 - 1 ,     n ≥ 1

Passo 1

Oláááá, caro estudante dedicado! Bora resolver esse exercício! Usaremos aqui o Princípio da Indução Finita (versão 2). Não lembra o que é? Toma aqui:

Lembrando que neste caso P n = 2 n + 1 - 1 .

Vamos começar a atacar a primeira condição, escolhendo n 0 = 1 como caso base:

a 1 = 3

P 1 = 2 1 + 1 - 1 = 3

Show, então P ( 1 ) é verdadeira. Mas não paramos por aí!

Como o nosso a n envolve os DOIS termos anteriores, precisamos que nossa hipótese de indução seja válida para dois “ n 0 ”. Para isto, vamos verificar se P ( 2 ) é verdadeira.

a 2 = 7

P 2 = 2 2 + 1 - 1 = 7

Maneiro! P ( 2 ) é verdadeira!

Passo 2

Vamos atacar a segunda condição. Supondo que seja válido para todo n 0 ≤ k < n , que é a nossa hipótese indutiva P ( k ) , queremos que seja válida para k + 1 também ( k + 1 pode estar tão próximo de n quanto se queira). Sendo que:

P k + 1 = 2 k + 2 - 1

Então, de alguma forma precisamos chegar aí. Vamos usar a relação:

a n = 3 a n - 1 - 2 a n - 2

Como queremos de k + 1 :

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

“Nossa, agora eu tô até feliz! ¬¬”

Caaaaalma, a gente sabe que foi válida até k , então também foi válida para k - 1 :

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

Agora nós vamos manipular os termos:

a k + 1 = 3.2 . 2 k - 3 - 2.2 k + 2

a k + 1 = 6.2 k - 2.2 k - 1

a k + 1 = 4.2 k - 1

a k + 1 = 2 k + 2 - 1

Como queríamos demonstrar, então P ( k + 1 ) é verdadeira.

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

Resposta

Demonstração por PIF versão 2 .