Define-se a sequência de Fibonacci como:
\[ \begin{cases} f_0 = 0 \\~\\ f_1 = 1 \\~\\ f_n = f_{n-1} +f_{n-2},\: n \geq 2\end{cases} \]Queremos provar que $\phi^n = f_n\cdot \phi +f_{n-1}$, onde $\phi = \dfrac{1+\sqrt{5}}{2}$, a solução positiva da equação $x^2 = x+1$.
A proposição vale para $n=2$, pois:
\[ \begin{align*} \phi^2 &= \left(\dfrac{1+\sqrt{5}}{2}\right)^2 \\~\\ &= \dfrac{1+2\sqrt{5}+5}{4} \\~\\ &= \dfrac{1+\sqrt{5}}{2}+1 \\~\\ &= 1\cdot\phi+1 \\~\\ &= f_2 \cdot \phi +f_1 \end{align*} \]Assumimos que vale para $n = k$, ou seja $\phi^k = f_k\cdot \phi +f_{k-1}$. Agora queremos provar que vale para $n = k+1$. Basta multplicar ambos os lados de $\phi^k = f_k\cdot \phi +f_{k-1}$ por $\phi$, resultando em $\phi^{k+1} = f_k\cdot \phi^2 +f_{k-1}\cdot \phi$, mas $\phi^2 = \phi+1$, então :
\[ \begin{align*} \phi^{k+1} &= f_k\cdot \phi^2 +f_{k-1}\cdot \phi \\~\\ &= f_k\cdot\left(\phi+1\right) +f_{k-1}\cdot \phi \\~\\ &= \phi\cdot\underbrace{\left(f_k+f_{k-1}\right)}_{f_{k+1}} +f_k \\~\\ &= f_{k+1} \cdot \phi + f_{k} \end{align*} \]Temos pelo princípio de indução que a proposição vale para qualquer $n \in \mathbb{N} $ maior que 2.