Solution

Suppose $F_n$ is the $n^{th}$ Fibbonacci number, find $F_{n+1}/F_{n}$ for the first 20 values of $n$. Use what you see to produce a way to approximate $F_n$.


$n$ $F_n$ $F_{n+1} / F_n$
0 1
1 1 1
2 2 2
3 3 1.5
4 5 1.666667
5 8 1.6
6 13 1.625
7 21 1.615385
8 34 1.619048
9 55 1.617647
10 89 1.618182
11 144 1.617978
12 233 1.618056
13 377 1.618026
14 610 1.618037
15 987 1.618033
16 1597 1.618034
17 2584 1.618034
18 4181 1.618034
19 6765 1.618034
20 10946 1.618034


Calculating the first 20 values of $F_{n+1}/F_{n}$ is straight-forward. The results are shown in the table on the left.

You can clearly see that the ratio $F_{n+1} / F_n$ appears to be very close to a constant for large values of $n$. More specifically, it appears that we are multiplying $F_n$ by roughly $1.618034$ each time to find $F_{n+1}$.

This suggests that we might be able to approximate $F_n$ with something of the following form:

$$F_n = C \cdot 1.618034^n$$

where $C$ is some constant.

Assuming the above is a good approximation and solving for $C$, we find $C \approx F_n / 1.618034^n$ when $n$ is large enough. For $n=20$, this yields $C \approx 0.723607$.

So it appears that we can approximate $F_n$ with the following formula:

$$F_n = 0.723607\cdot 1.618034^n$$

Indeed, this formula does a great job approximating $F_n$, predicting its value exactly (provided one rounds to the nearest integer) all the way up to $n=29$. Further, had we better approximated the apparent constant $1.618034...$, the resulting formula would have worked all that much longer.

This begs the question, however -- what is the exact value of the constant $1.618034...$ that we seek, and is there anything significant about it? Hmmm....