Seja a sequência h0, h1, h2, cdots definida como
l h0=1 h1=2 h2=3 hk=hk-1+hk-2+hk-3, forall inteiros k >= 3
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:
  1. Base da Indução: Mostramos que a afirmação vale para os primeiros valores, geralmente $ n = 0 $ e alguns outros.
  2. 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} $. ✅

Exercícios relacionados