<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] Let $\phi=\dfrac{\sqrt{5}+1}2$ and note that $\phi^{-1} =\dfrac 1\phi= \dfrac{\sqrt{5}-1}2$.
Note also that $1+\dfrac 1\phi=\phi$ and $1-\phi=-\dfrac 1\phi$.
From your formula,
$$F_n = \frac 1{\sqrt{5}}\left[\phi^n-(-\frac 1\phi)^n \right]$$
For $n=k$ and $n=k-1$,
$$\begin{align}
F_k &= \frac 1{\sqrt{5}}\left[\phi^k-(-\frac 1\phi)^k \right]\\
F_{k-1} &= \frac 1{\sqrt{5}}\left[\phi^{k-1}-(-\frac 1\phi)^{k-1} \right]\\
&=\frac 1{\sqrt{5}} \left[\phi^k \cdot \frac 1\phi -(-\frac 1\phi)^k \cdot (-\phi)\right]\\
\end{align}$$
Hence,
$$\begin{align}
F_{k+1}&=F_{k}+F_{k-1}\\
&=\frac 1{\sqrt{5}} \left[\phi^k \cdot \left( 1+\frac 1\phi \right) 
-(-\frac 1\phi)^k \cdot \left( 1-\phi \right)\right]\\
&=\frac 1{\sqrt{5}} \left[\phi^k \cdot \phi 
-(-\frac 1\phi)^k \cdot \left( -\frac 1\phi \right)\right]\\
&=\frac 1{\sqrt{5}} \left[\phi^{k+1}-(-\frac 1\phi)^{k+1} \right]
\end{align}$$
i.e. if formula is true for $n=k-1$ and $n=k$, it is also true for $n=k+1$.
For $n=0$ and $n=1$, $F_0=0$ and $F_1=1$ respectively. 
Hence $F_2=F_0+F_1=1$. 
It can easily be shown that the formula is true for $n=2$.
Hence, by induction, formula is true for all positive integer $n\geq 2$.
</s>