1.5a Lösning 11

Påstående:       \( \displaystyle F(n) = {1\over\sqrt{5}}\,\left({1+\sqrt{5}\over 2}\right)^n\,-\;{1\over\sqrt{5}}\,\left({1-\sqrt{5}\over 2}\right)^n\; , \qquad n \;\mbox{heltal } \geq 1 \)

där \( F(n) \, \) är Fibonaccis funktion:

\[ F(n) \, = \, \begin{cases} 1 & \mbox{om } n = 1 \\ 1 & \mbox{om } n = 2\; \\ F(n-1) + F(n-2) & \mbox{om } n = 3,\,4,\,5,\,\cdots \end{cases} \]

Bevis: Vi visar påståendet för \( n = 1 \):

\[ F(1)\;=\;{1\over\sqrt{5}}\,\left({1+\sqrt{5}\over 2}\right)\,-\;{1\over\sqrt{5}}\,\left({1-\sqrt{5}\over 2}\right) = {1\over\sqrt{5}}\,\left({1\over 2}+{\sqrt{5}\over 2}\right)\,-\;{1\over\sqrt{5}}\,\left({1\over 2}-{\sqrt{5}\over 2}\right) = \]

\[ =\;{1 \over 2\,\sqrt{5}}\;+\;{1\over 2}\;-\;{1 \over 2\,\sqrt{5}}\;+\;{1\over 2}\;=\;1 \]

Vi visar påståendet för \( n = 2 \):

\[ F(2)\;=\;{1\over\sqrt{5}}\,\left({1+\sqrt{5}\over 2}\right)^2\,-\;{1\over\sqrt{5}}\,\left({1-\sqrt{5}\over 2}\right)^2 =\;{1\over 4\,\sqrt{5}}\,({1+\sqrt{5}})^2\;-\;{1\over 4\,\sqrt{5}}\,({1-\sqrt{5}})^2\;= \]

\[ =\;{1\over 4\,\sqrt{5}}\,\left[(1+\sqrt{5})^2\;-\;(1-\sqrt{5})^2\right]\;= \;{1\over 4\,\sqrt{5}}\,[1+2\,\sqrt{5}+5\;-\;(1-2\,\sqrt{5}+5)]\;=\;1 \]

För påståendet med godtyckliga \( n\, \) inför vi nya beteckningar:

\[ c_1 = {1\over\sqrt{5}} \qquad\qquad\qquad\quad c_2 = -\,{1\over\sqrt{5}} \]

\[ r_1 = {1\,+\,\sqrt{5}\over 2} \qquad\qquad\; {\color{White} x} r_2 = {1\,-\,\sqrt{5}\over 2} \]

Då får påståendet följande form:

\[ F(n) \, = \, c_1\:r_1\,^n\;+\;c_2\:r_2\,^n \]

Vi bildar med denna form \( F(n-1) \, \) och \( F(n-2) \, \) och visar Fibonaccis rekursionsformel:

\[ F(n) = F(n-1) + F(n-2)\, \]

\[ F(n-1)\,=\,c_1\:r_1\,^{n-1}\;+\;c_2\:r_2\,^{n-1}\,=\,c_1\:r_1^n\,r_1^{-1}\;+\;c_2\:r_2^n\,r_2^{-1} \,=\,c_1\:r_1^n\,{1\over r_1}\;+\;c_2\:r_2^n\,{1\over r_2} \]

\[ F(n-2)\,=\,c_1\:r_1\,^{n-2}\;+\;c_2\:r_2\,^{n-2}\,=\,c_1\:r_1^n\,r_1^{-2}\;+\;c_2\:r_2^n\,r_2^{-2} \,=\,c_1\:r_1^n\,{1\over r_1^2}\;+\;c_2\:r_2^n\,{1\over r_2^2} \]

\[ F(n-1) + F(n-2)\,=\, c_1\:r_1^n\,{1\over r_1}\,+\,c_2\:r_2^n\,{1\over r_2}\,+\,c_1\:r_1^n\,{1\over r_1^2}+c_2\:r_2^n\,{1\over r_2^2} \,=\, \]

\[ c_1\:r_1^n\,\left({1\over r_1}+{1\over r_2^2}\right)\,+\, \]