Question

A sequência de Fibonacci é definida indutivamente como $F_1 = F_2 = 1$ e $F_{n + 2} = F_{n + 1} + F_n$. Mostre que $F_n \ \textless \ 2^n$ para todo $n$ natural com $n \geq 1$.

Sugestão: PIF

Answer 1

Avaliando a validade para $n=1$:

$F_{1}:=1~\ \textless~2^{1}=2~~(v\'alido)$

Avaliando a validade para $n=2$:

$F_{2}:=1~\textless~2^{2}=4~~(v\'alido)$

Usaremos outra forma do princípio da indução: Assumimos que a propriedade é válida para todos os $n\in[1,~k-1]\subset\mathbb{N}$, e mostramos que também vale para $n=k$

Da definição da sequência, temos

$F_{k+1}=F_{k}+F_{k-1}$

Mas, por hipótese de indução, $F_{k}~\textless~2^{k}$ e $F_{k-1}~\textless~2^{k-1}$, logo

$F_{k+1}~\textless~2^{k}+2^{k-1}$

Colocando $2^{k+1}$ em evidência:

$F_{k+1}~\textless~2^{k+1}\cdot(2^{-1}+2^{-2})\\\\F_{k+1}~\textless~2^{k+1}\cdot(\frac{1}{2}+\frac{1}{4})\\\\F_{k+1}~\textless~\frac{3}{4}\cdot2^{k+1}$

Como $\frac{3}{4}~\textless~1$ e $2^{k+1}~\textgreater~0~\forall~k\in\mathbb{R}$, temos

$\frac{3}{4}\cdot2^{k+1}~\textless~1\cdot2^{k+1}~~\therefore~~\frac{3}{4}\cdot2^{k+1}~\textless~2^{k+1}$

Então:

$F_{k+1}~\textless~\frac{3}{4}\cdot2^{k+1}~\textless~2^{k+1}\\\\\\\boxed{\boxed{F_{k+1}~\textless~2^{k+1}}}$

Portanto, pelo princípio da indução, $F_{n}~\textless~2^{n}~\forall~n\ge1~(inteiro)$