Indução para provar que a sequência de Fibonacci cresce exponencialmente rápido [duplicar]

Question

Como resolver isso usando indução?

Use indução para provar que

$F_n\ge2^{\frac n2}\;,\;$ para $n\ge6\;.$

$F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$

Answer 1

Existem três etapas para qualquer problema de indução.

Etapa 1, provar seus casos básicos. Neste caso, primeiro mostre que$F(n)\geq 2^\frac n2$ quando $n=6$ (ie $F(6)\geq 2^3=8$) Trabalhando fora$F(6)$é suficiente aqui. Uma vez que a definição recursiva é baseada em dois casos anteriores ($F(n)=F(n-1)+F(n-2)$, existem dois termos no RHS), você também precisa de um segundo caso base, o próximo ao longo, aqui está $n=7$então mostre isso $F(7)\geq 2^\frac 72$ (Dica: eleve ao quadrado este número para encontrar seu valor numérico aproximado)

Etapa 2, suponha que a propriedade seja verdadeira para um determinado $k,k+1$. Ou seja, suponha$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

Etapa 3: use isso para provar que a afirmação é válida para o próximo caso, ou seja, que $(1)$ implica que $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$

Answer 2

$F_6=8\ge2^{\frac62}\;.$

$F_7=13\ge\sqrt{2^7}=2^{\frac72}\;.$

Para agora $\;n\ge8\;,$ nós supomos que $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ e provar isso $\;F_n\ge2^\frac n2.$

$F_n=F_{n-1}+F_{n-2}\ge2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}}\big(\sqrt 2+1\big)\ge$

$\ge2^{\frac n2-1}\cdot 2=2^{\frac n2}.$

Portanto, por indução em $n$, segue que

$F_n\ge2^\frac n2\quad$ para todos $\;n\ge6\;.$