It turns out that the Fibonacci sequence satisfies the following explicit formula: For all integers $F_{n} ≥ 0$,
$F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1}]$
Verify that the sequence defined by this formula satisfies the recurrence relation $F_{k} = F_{k-1} + F_{k-2}$ for all integers $k ≥ 2$.
$$F_{k} = \frac{\phi^k + \psi^k}{\sqrt{5}}$$ $$F_{k-1} + F_{k-2} = \frac{\phi^{k-1} + \psi^{k-1}}{\sqrt{5}} + \frac{\phi^{k-2} + \psi ^{k-2}}{\sqrt{5}}$$ $$= \frac{1}{\sqrt{5}} \left(\phi^{k-2} + \psi ^{k-2} + \phi^{k-1} + \psi^{k-1}\right)$$
From here see that $$\phi^{k-2} + \phi^{k-1} = \phi^{k-2}(\phi + 1) = \phi^{k-2}\left(\frac{3+\sqrt{5}}{2}\right)$$ $$ = \phi^{k-2}\left(\frac{6+2\sqrt{5}}{4}\right) = \phi^{k-2}\left(\frac{1+2\sqrt{5}+5}{4}\right) = \phi^{k-2}\left(\frac{1+\sqrt{5}}{2}\right)^2 = \phi^{k-2}\phi^2 = \phi^k$$
Similarily $$\psi^{k-2} + \psi^{k-1} = \psi^{k-2}(\psi + 1) = \psi^{k-2}\left(\frac{3-\sqrt{5}}{2}\right) $$ $$ = \psi^{k-2}\left(\frac{6-2\sqrt{5}}{4}\right) = \psi^{k-2}\left(\frac{1-2\sqrt{5}+5}{4}\right) = \psi^{k-2}\left(\frac{1-\sqrt{5}}{2}\right)^2 = \psi^{k-2}\psi^2 = \psi^k$$
Therefore, we get that
$$F_{k-1} + F_{k-2} = \frac{\phi^k + \psi^k}{\sqrt{5}}$$