3.2-7

3.2-7 Prove by induction that the i th Fibonacci number satisfies the equality $$F_i = {\theta^i - \widehat{\theta}^i \over\sqrt5}$$ where $\theta$ is the golden ratio and $\widehat{\theta}$ is its conjugate. Solution: $$x^2 = x -1$$ Roots of the above equation are golden ratio and conjugate substituting roots in the equation $$\theta^2 = \theta+1$$ multiplying both sides of the equation with $\theta^{k}$ $$\theta^{k+2} = \theta^{k+1}+\theta^{k} $$ which is true for conjugate as well $$\widehat{\theta}^{k+2} = \widehat{\theta}^{k+1}+\widehat{\theta}^k $$ Lets suppose \begin{equation}\label{eq:1} F(k) = {\theta^k - \widehat{\theta}^k \over\sqrt5} \end{equation} and \begin{equation}\label{eq:2} F(k+1) = {\theta^{k+1} - \widehat{\theta}^{k+1} \over\sqrt5} \end{equation} factorial of number can be defined by the following equation $$F(n) = F(n-1)+F(n-2)$$ The factorial of a number $ F(k+2)$ is $$F(k+2) = F(k+1)+F(k)$$ substituting $F(k+1)$ and $F(k)$ from above assumptions (\ref{eq:1}) and (\ref{eq:2}) $$F(k+2) = {\theta^k - \widehat{\theta}^k \over\sqrt5} + {\theta^{k+1} - \widehat{\theta}^{k+1} \over\sqrt5} $$ $$F(k+2) = {\theta^k +\theta^{k+1} \over\sqrt5} - ({\widehat{\theta}^{k+1} +\widehat{\theta}^k \over\sqrt5}) $$ $$F(k+2) = {\theta^{k+2} \over\sqrt5} - ({\widehat{\theta}^{k+2}\over\sqrt5}) $$ Thus, by the mathematical induction principle, we conclude that $$F_i = {\theta^i - \widehat{\theta}^i \over\sqrt5}$$