Vi löser rekursionsekvationen $x^{n+2} = x^{n+1} + x^n$ :

x^{n+2} = x^{n+1} + x^n \iff x^n(x^2 - x - 1) = 0 \iff x^2 - x - 1 = 0,

om $x \neq 0$ . Denna ekvation har lösningarna

A = \frac{1 + \sqrt{5}}{2}, \quad B = \frac{1 - \sqrt{5}}{2},

dvs $A^n + 2 = A^{n+1} + A^n$ och $B^{n+2} = B^{n+1} + B^n$ .
Det betyder att $G(n) = aA^n + bB^n$ uppfyller

\begin{aligned} G(n + 2) &= aA^{n+2} + bB^{n+2} \\ &= a(A^{n+1} + A^n) + b(B^{n+1} + B^n) \\ &= aA^{n+1} + bB^{n+1} + aA^n + bB^n \\ &= G(n + 1) + G(n), \end{aligned}

dvs rekursionssambandet.
Vi bestämmer $a$ och $b$ så att $G(1) = 1$ och $G(2) = 1$ :

\begin{aligned} &\left\{ \begin{array}{l} aA + bB = 1 \\ aA^2 + bB^2 = 1 \end{array} \right. \\ &\Longleftrightarrow \left\{ \begin{array}{l} aA + bB = 1 \\ a(A + 1) + b(B + 1) = 1 \end{array} \right. \\ &\Longleftrightarrow \left\{ \begin{array}{l} aA + bB = 1 \\ a + b = 0 \end{array} \right. \\ &\Longleftrightarrow \left\{ \begin{array}{l} a(A - B) = 1 \\ b = -a \end{array} \right. \\ &\Longleftrightarrow \left\{ \begin{array}{l} a = \frac{1}{\sqrt{5}} \\ b = -\frac{1}{\sqrt{5}}, \end{array} \right. \end{aligned}

Där vi använt att $A$ och $B$ är lösningar till ekvationen $x^{2} - x - 1 = 0$ i första steget, och att $A - B = \sqrt{5}$ i sista steget.
$F(1) = G(1), F(2) = G(2)$ , och om $G(k) = F(k)$ för $k \leq n$ så är $G(n+1) = F(n+1)$ då både $G$ och $F$ uppfyller samma rekursionssamband. Därför är $G(n) = F(n)$ för alla $n$ enligt indutkionsprincipen, dvs

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.

Svar: $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$