Die Induktion zum Nachweis der Fibonacci-Sequenz wächst exponentiell schnell [doppelt]

Nov 27 2020

Wie kann man das mit Induktion lösen?

Verwenden Sie die Induktion, um dies zu beweisen

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

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

Antworten

RhysHughes Nov 27 2020 at 22:29

Jedes Induktionsproblem besteht aus drei Schritten.

Schritt 1, beweisen Sie Ihre Basisfälle. Zeigen Sie in diesem Fall zunächst , dass$F(n)\geq 2^\frac n2$ wann $n=6$ (dh $F(6)\geq 2^3=8$). Ausarbeiten$F(6)$reicht hier aus. Da die rekursive Definition auf zwei früheren Fällen basiert ($F(n)=F(n-1)+F(n-2)$, es gibt zwei Begriffe auf der RHS), Sie benötigen auch einen zweiten Basisfall, den nächsten, hier also $n=7$, also zeig das $F(7)\geq 2^\frac 72$ (Hinweis: Quadrieren Sie diese Zahl, um den ungefähren numerischen Wert zu ermitteln.)

Schritt 2: Angenommen, die Eigenschaft gilt für eine bestimmte Eigenschaft $k,k+1$. Das heißt, nehmen Sie an$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

Schritt 3: Verwenden Sie dies, um zu beweisen, dass die Aussage für den nächsten Fall gilt, dh das $(1)$ impliziert, dass $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$

Angelo Nov 27 2020 at 22:37

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

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

Jetzt für $\;n\ge8\;,$ wir nehmen das an $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ und beweise das $\;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}.$

Daher durch Induktion auf $n$, es folgt dem

$F_n\ge2^\frac n2\quad$ für alle $\;n\ge6\;.$