Prove por indução matemática que hn <= 3^n para todos inteiros n >= 0.
Passo 1
Beleza, vamos lá! A gente tem uma sequência definida assim:
h0 = 1 h1 = 2 h2 = 3 hk = hk-1 + hk-2 + hk-3, forall k >= 3
O que a gente precisa provar é que para todo número inteiro $ n \geq 0 $, $ h_{n} \leq 3^{n} $. Para isso, vamos usar indução matemática, que é uma técnica para provar que uma propriedade vale para todos os números naturais.
Passo 2
Primeiro, vamos entender o que é indução matemática. Basicamente, a gente faz dois passos:
Base da Indução: Mostramos que a afirmação vale para os primeiros valores, geralmente $ n = 0 $ e alguns outros.
Passo Indutivo: Assumimos que a afirmação vale para alguns valores até $ k $ e mostramos que, com isso, ela também vale para $ k+1 $.
Vamos começar com a base da indução.
Passo 3
Base da Indução:
Vamos verificar para $ n = 0, 1, 2 $:
Para $ n = 0 $:
n = 0, 1, 2
Para $ n = 1 $:
n = 0
Para $ n = 2 $:
h0 = 1 <= 3^0 = 1 (Verdadeiro)
Então, a base da indução está certa.
Passo 4
Passo Indutivo:
Agora, vamos assumir que a afirmação vale para todos os $ n $ até $ k $. Ou seja, assumimos que:
n
Com essa suposição, precisamos mostrar que $ h_{k+1} \leq 3^{k+1} $.
Passo 5
Vamos usar a definição da sequência para $ h_{k+1} $:
hk+1
Pela nossa hipótese de indução, sabemos que cada um desses termos é menor ou igual a $ 3^{k} $, $ 3^{k-1} $ e $ 3^{k-2} $, respectivamente.
Passo 6
Substituindo as desigualdades:
hk+1 <= 3^k + 3^k-1 + 3^k-2
Agora, vamos simplificar essa expressão para ver se conseguimos chegar em $ 3^{k+1} $.
Passo 7
Fatorando $ 3^{k-2} $ dos três termos:
3^k-2
Observamos que $ 13 $ é maior que $ 9 $, mas queremos mostrar que $ 3^{k-2} \times 13 \leq 3^{k+1} $.
Passo 8
Vamos comparar $ 13 $ com $ 3^{3} = 27 $. De fato, $ 13 < 27 $, então:
13
Portanto:
3^3 = 27
Resposta
Assim, por indução matemática, mostramos que para todo inteiro $ n \geq 0 $, $ h_{n} \leq 3^{n} $. ✅