Lesson 1

A recurrence relation is an equation where the same function appears on both sides but with different parameters. As we have seen multiple times, recurrence relations often arise naturally in counting problems.

One of the most famous such relations is the recurrence definition of Fibonacci numbers: \[F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)+F(n-2).\] This defines the following sequence of numbers:

A recurrence relation can be mechanically transformed into a recursive method for computing the corresponding value. To avoid a combinatorial explosion during such computation, it is necessary to save all intermediate results (this is called memoization).

from functools import cache


@cache
def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)


print(fib(100))

354224848179261915075

The solution to a recurrence relation is an explicit formula for the corresponding expression. For example, the Fibonacci numbers have the Binet formula: \[F(n)=\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^{n}-\left(\frac{1-\sqrt 5}{2}\right)^{n}\right) \ .\] This formula appears surprising. First, it is unclear why irrational numbers appear in a formula for an integer sequence. Second, while the formula is not difficult to prove by mathematical induction, it is unclear how it could be derived. Indeed, the formula was discovered six centuries after the sequence was introduced. Today, this formula for Fibonacci numbers, as well as for many other recurrence relations, can be obtained using Python.

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), {f(0): 0, f(1): 1}))

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