Question

Prove that the Fibonacci sequence {fn}∞n=1 defined in Lecture 7-8 has the following formula: 1+√ fn+1 := 2 n 5 √ n 5 −1−√ 2 5 (n ≥ 0)

Answer 1

$P_n: F(n)=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt5}{2}\right)^{n+1}\right] \text{ is true for }n\in \mathbb{N}\\\;\\ \text{For }n=0, \; F(0)=\dfrac{1}{\sqrt5}\times \dfrac{2\sqrt5}{2}=1~~~~~~ \\\text{which follows that }P_0 \text{ is true.}\\ \text{Let $P_x$ is true for $\forall x\ni x\leq k\in \N$}\\\;\\ \therefore F(k)=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k+1}-\left(\dfrac{1-\sqrt5}{2}\right)^{k+1}\right] \\\;\\ \text{and, $F(k-1)=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k}-\left(\dfrac{1-\sqrt5}{2}\right)^{k}\right] $}\\~\\ \text{Now, $F(k+1)=F(k)+F(k-1)$}\\ \text{So,}\\ F(k)+F(k-1)=\\ = \dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k+1}-\left(\dfrac{1-\sqrt5}{2}\right)^{k+1}\right]+ \dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k}-\left(\dfrac{1-\sqrt5}{2}\right)^{k}\right]\\ \;\\=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k}\left(1+\dfrac{1+\sqrt5}{2}\right)-\left(\dfrac{1-\sqrt5}{2}\right)^{k}\left(1+\dfrac{1-\sqrt5}{2}\right)\right] \\\;\\ =\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k}\left(\dfrac{1+\sqrt5}{2}\right)^2-\left(\dfrac{1-\sqrt5}{2}\right)^{k}\left(\dfrac{1-\sqrt5}{2}\right)^2\right]\\\;\\ =\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{k+2}-\left(\dfrac{1-\sqrt5}{2}\right)^{k+2}\right]=F(k+1).$

$\\\;\\\text{$\therefore P_{k+1}$ is true.\\ }\\ \text{So, by theorem of Mathematical Induction, $P_n \text{ is true $\forall n\in \N$}$}$

$$\therefore \boxed{ F(n)=\dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt5}{2}\right)^{n+1}\right]}~~~~~\text{(Proved)}$$