1. Seja a_{n}, n \geq 1 uma sequência definida por
\begin{aligned} & \quad a_{1}=1, a_{2}=2, a_{3}=3 \\\ & a_{n}=a_{n-1}+a_{n-2}+a_{n-3} \text { para } n \geq 4 \end{aligned}
Prove que a_{n}<2^{n} para todo n \geq 1.

Passo 1

O enunciado define a sequência (a_n) por
a_{1}=1,\quad a_{2}=2,\quad a_{3}=3,
e para n\ge4 a_{n}=a_{n-1}+a_{n-2}+a_{n-3}.
O que queremos mostrar é que
a_{n}<2^{n}
para todo n\ge1. Vamos usar o princípio da indução matemática.

Passo 2

Verificamos os casos iniciais n=1,2,3:
Para n=1: temos a_{1}=1 e 2^{1}=2, logo 1<2.
Para n=2: temos a_{2}=2 e 2^{2}=4, logo 2<4.
Para n=3: temos a_{3}=3 e 2^{3}=8, logo 3<8.
Assim, a desigualdade vale para n=1,2,3.

Passo 3

Suponha agora que a propriedade a_{k}<2^{k} seja verdadeira para todo k com 1\le k\le n-1, onde n\ge4. Essa é a hipótese de indução.

Passo 4

Usando a hipótese de indução e a definição recursiva, para n\ge4 temos
a_{n} = a_{n-1}+a_{n-2}+a_{n-3} < 2^{\,n-1}+2^{\,n-2}+2^{\,n-3}.
Agora fatoramos 2^{\,n-3}:
2^{\,n-1}+2^{\,n-2}+2^{\,n-3} =2^{\,n-3}\bigl(2^{2}+2^{1}+1\bigr) =2^{\,n-3}\cdot7.
Como 7<8, segue que
2^{\,n-3}\cdot7 < 2^{\,n-3}\cdot8 = 2^{\,n},
logo
a_{n} < 2^{\,n}.
Isso fecha o passo indutivo.

Resposta

Portanto, por indução, a_{n}<2^{n} para todo n\ge1.

Exercícios relacionados