Lesson 2

We already have enough intuition to understand that Fibonacci numbers grow exponentially. This can be seen, for example, as follows. It is clear that the sequence \(F(n)\) is non-decreasing. Thus, \[2F(n-2) \le F(n-1)+F(n-2) \le 2F(n-1) \ .\] The solutions to the relations \(F(n)=2F(n-2)\) and \(F(n)=2F(n-1)\) are straightforward: \(\sqrt{2}^{n}\) and \(2^{n}\). It is reasonable to hypothesize that \(F(n)\) also grows as \(\alpha^{n}\) for some \(\sqrt{2}\le \alpha \le 2\). This is just a guess, but we can verify it against the recurrence relation. Let us try! If \[\alpha^{n} = \alpha^{n-1}+\alpha^{n-2},\] then \[\alpha^{2}=\alpha+1.\] It follows that the exponential functions \(G(n)=\alpha_{1}^{n}\) and \(H(n)=\alpha_{2}^{n}\), where \[\alpha_{1,2}=\frac{1\pm \sqrt{5}}{2},\] are the roots of the resulting quadratic equation and satisfy the recurrence relation.

A simple but crucial observation is that any linear combination \(aH(n)+bG(n)\) (where \(a\) and \(b\) are constants) also satisfies our recurrence relation. Indeed, let \(Q(n)=aH(n)+bG(n)\). Then \[\begin{align*}Q(n)&=aH(n)+bG(n)=\\&=a(H(n-1)+H(n-2))+b(G(n-1)+G(n-2))=\\&=(aH(n-1)+bG(n-1))+(aH(n-2)+bG(n-2))=\\&=Q(n-1)+Q(n-2) \ .\end{align*}\] The function \(Q(n)\) is called the general solution of the recurrence relation.

Now it is time to recall that the functions \(H(n)\) and \(G(n)\) arose as solutions to the recurrence relation, but without considering initial conditions. Clearly, they do not satisfy the initial conditions: \(H(0)=G(0)=1 \neq 0\). This explains the need for linear combinations: we adjust the coefficients \(a\) and \(b\) so that the initial conditions are satisfied! These coefficients can be found by solving a system of two linear equations: \[\begin{cases}0=a+b\\ 1=a\alpha_1+b\alpha_2\end{cases}\] This leads to Binet’s formula.

This is exactly what the \(\texttt{rsolve}\) method in Python does. It finds the roots \(\alpha_{1}\) and \(\alpha_{2}\) of the characteristic polynomial \(\alpha^{n}=\alpha^{n-1}+\alpha^{n-2}\), understanding that any linear combination \(\alpha_{1}^{n}\) and \(\alpha_{2}^{n}\) satisfies the recurrence relation. If initial conditions are provided, it derives the coefficients for the linear combination from them.

from sympy import Function, rsolve
from sympy.abc import n

f = Function('f')
Fib = f(n) - f(n - 1) - f(n - 2)

print(rsolve(Fib, f(n)))
print(rsolve(Fib, f(n), {f(0): 0, f(1): 1}))

C0*(1/2 - sqrt(5)/2)**n + C1*(1/2 + sqrt(5)/2)**n
-sqrt(5)*(1/2 - sqrt(5)/2)**n/5 + sqrt(5)*(1/2 + sqrt(5)/2)**n/5