Fibonnaci sequence
Task number: 2801
Prove by mathematical induction that for the Fibonacci sequence \(F_1=F_2=1\), \(F_n=F_{n-1}+F_{n-2}\) the following holds: \(\displaystyle \sqrt{5}F_n= \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \).
Resolution
For \(n=1\) we have \(\sqrt{5}=\frac{1+\sqrt5}2-\frac{1-\sqrt5}2\).
For \(n=2\) we have \(\sqrt{5}=\frac{3+\sqrt5}2-\frac{3-\sqrt5}2=\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^2\).
We prove the statement for \(n+1\) given that it holds for \(n\) and \(n-1\):
\(\displaystyle \sqrt{5}F_{n+1}=\sqrt{5}F_n+\sqrt{5}F_{n-1}= \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n+ \left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}= \)
\(= \left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1+\sqrt{5}}{2}\right)^{n-1} -\left[\left(\frac{1-\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right]= \left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \)
