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 att visa påståendet för 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_1^2}\right) \,+\, c_2\:r_2^n\,\left({1\over r_2}+{1\over r_2^2}\right) \, = \, c_1\:r_1^n\;+\;c_2\:r_2^n \, = \, F(n) \; {\rm , \; därför\;att:}$$

$${1\over r_1} + {1\over r_1^2} = {2 \over 1+\sqrt{5}} + {4 \over (1+\,\sqrt{5})^2} = {2(1+\sqrt{5}) + 4 \over (1+\sqrt{5})^2} = {6+2\,\sqrt{5} \over 1+2\sqrt{5}+5} = {6+2\,\sqrt{5} \over 6+2\sqrt{5}} = 1$$

$${1\over r_2} + {1\over r_2^2} = {2 \over 1-\sqrt{5}} + {4 \over (1-\,\sqrt{5})^2} = {2(1-\sqrt{5}) + 4 \over (1-\sqrt{5})^2} = {6-2\,\sqrt{5} \over 1-2\sqrt{5}+5} = {6-2\,\sqrt{5} \over 6-2\sqrt{5}} = 1$$