<s>[INST] Inductive proof of a formula for Fibonacci numbers May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: 
$$F_n=\frac{1}{\sqrt{5}}⋅\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}⋅\left(\frac{1-\sqrt{5}}{2}\right)^n.$$
I tried to put $n=1$ into the equation and prove that if $n=1$ works then $n=2$ works and it should work for any number, but it didn't work. I need to prove that this formula gives the $n$th Fibonacci number.
 [/INST] Proof: Let n=1 thus,
\begin{align*}
F_1&=\frac{(\frac{1+\sqrt{5}}{2})^{1}-(\frac{1-\sqrt{5}}{2})^{1}}{\sqrt{5}}\\
&=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}\\
&=\frac{\frac{1+\sqrt{5}-1+\sqrt{5}}{2}}{\sqrt{5}}\\
&=\frac{\frac{\sqrt{5}+\sqrt{5}}{2}}{\sqrt{5}}\\
&=\frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}}\\
&=\frac{{\sqrt{5}}}{\sqrt{5}}\\
&=1
\end{align*}
Suppose
\begin{equation}
F_k=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}
\end{equation}
Also $F(k+1)=F(k)+F(k-1)$
\begin{align*}
F(k)+F(k-1)&=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}+\frac{(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\
&=\frac{(\frac{1+\sqrt{5}}{2})^{k}+(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\
&=\frac{((\frac{1+\sqrt{5}}{2})+1)(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})+1)(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\
&=\frac{((\frac{3+\sqrt{5}}{2}))(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{3-\sqrt{5}}{2}))(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\
&=\frac{((\frac{1+\sqrt{5}}{2})^{2})(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})^{2})(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\
&=\frac{(\frac{1+\sqrt{5}}{2})^{k+1}-(\frac{1-\sqrt{5}}{2})^{k+1}}{\sqrt{5}}\hfill 
\end{align*}
</s>