In this series of short blog posts, I will try to go into detail regarding the Fibonacci sequence in particular, and linear recurrences in general. This first part discusses the Fibonacci sequence, ending with a closed form solution. Part two will go into detail regarding implementation in code, and part three will generalize the first two parts for general linear recurrences.
You probably all know the Fibonacci sequence, but just in case you've forgotten, let me refresh your memories. The classic example is about rabbit populations, so we will use that as a starting point.
Let's say we release two rabbits (a male and female) into the wild. Rabbits are able to mate at the age of 1 month, so that at the end of 2 months the female can produce another pair of rabbits. Rabbits will never die, and mating always produces another pair (a male and a female).
How many rabbit pairs will there be at the end of one year?
Working it out on a piece of scratch paper, we get something like this:
- After one month, the rabbits mate, but there is still only one pair.
- After two months, the female produces another pair, so there are now 2 rabbit pairs in the field.
- After three months, the original female produces another pair, leading to 3 rabbit pairs.
- At the end of four months, the original female produces yet another pair, and the female born two months ago also produces a pair, making 5 pairs total.
It seems that at the end of each month the number of rabbit pairs is the sum of the number of rabbit pairs in the previous two months. This makes sense, as rabbits do not die, so the population of the previous month is still alive, and all females that are at least two months old give birth to a pair of rabbits.
We can write this formally as:
$F(n) = F(n-1) + F(n-2), \forall n \geq 2$
with $F(1) = 1$, $F(0) = 0$.
The first 10 terms of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
Definition 1. A linear homogeneous recurrence relation is an equation of the form:
$f(n) = \sum\limits_{i=1}^{d} a_{i} f(n-i)$
where all the $a_{i}$ are constants.
In the Fibonacci example, $a_{1} = 1, a_{2} = 1$. To solve a linear recurrence relation, one thing we could try to do is guess the solution. The Fibonacci example looks as if it was increasing exponentially, so we can try the guess $F(n) = cx^n$ for some constant $c$.
Replacing in the recurrence relation, we get $cx^n = cx^{n-1} + cx^{n-2}$. Dividing by $cx^{n-2}$ throughout, we are left with the quadratic $x^2 - x - 1 = 0$, which has solutions $\frac{1 \pm \sqrt{5}}{2}$.
So we have two solutions to the recurrence relation:
$F(n) = c(\frac{1 + \sqrt{5}}{2})^n$ $F(n) = c(\frac{1 - \sqrt{5}}{2})^n$
We will digress a bit before arriving at a closed form solution.Theorem 1. If $f(n)$ and $g(n)$ are two solutions to a recurrence relation, then any linear combination of the two is also a recurrence relation.
Proof. We know that $f(n)$ and $g(n)$ both satisfy the recurrence relation:
$f(n) = \sum\limits_{i=1}^{d} a_{i} f(n-i)$ $g(n) = \sum\limits_{i=1}^{d} a_{i} g(n-i)$
A linear combination of the two yields:
$cf(n)+dg(n) = \sum\limits_{i=1}^{d} a_{i}(c f(n-i) + d g(n-i))$
Using this theorem we can write $F(n) = c_1 (\frac{1 + \sqrt{5}}{2})^n + c_2 (\frac{1 - \sqrt{5}}{2})^n$. Substituting $n=0$ gives us:
$F(0) = c_1 (\frac{1 + \sqrt{5}}{2})^0 + c_2 (\frac{1 + \sqrt{5}}{2})^0 = c_1 + c_2 = 0$
The second boundary condition ($n=1$) yields:
$F(1) = c_1 (\frac{1 + \sqrt{5}}{2}) + c_2(\frac{1 - \sqrt{5}}{2}) = 1$
Solving the system of linear equations gives us $c_1 = \frac{1}{\sqrt{5}}$, $c_2 = -\frac{1}{\sqrt{5}}$. We thus have a closed form solution for the Fibonacci sequence:
$F(n) = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1 - \sqrt{5}}{2})^n$
Part two will be about solving recurrences in code.
No comments:
Post a Comment