# 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....