Fibonacci
A general formula for Fn. (A combinatoric approach)
Like in the intoduction, we want to build a stone path. The path is 1 inch wide and is n inches long.
There are 2 kinds of stones, namely 1 inch x 1 inch stones and 1 inch x 2 inch stones.
For the moment let n=8.
Here you see an example of a path of length 8 with 4 1x1 stones and 2 1x2 stones.
During the building of the path we choose a 1x1 stone with probability p, and a 1x2 stone with
probability q (=1-p). If q = p2,
then each path of length 8 will be build with equal probability, namely p8 !
There are, as we already know from the introduction, F9 ways to build a path of length 8.
So, the probability for a path of length 8 is F9 p8.
If there does not arise a path of length 8, then there is constructed a path of length 7 followed by a stone of length 2.
The number of those paths is F8, so the probability that
there will not arise a path of length 8 is F8 p9.
Now we may conclude that F9 p8 + F8 p9 = 1, and in general
Fn+1 pn + Fn pn+1 = 1 with p + p2 = 1 (or p = (
5 - 1)/2 ).
Then (with r=1/p and s=-p) Fn+1 = rn + sFn.
Thus Fn+1 = rn + sFn = rn + rn-1s + Fn-1 s2 = ... =
rn + rn-1s + rn-2s2 + rn-3s3 + ... + sn =
(rn+1-sn+1)/(r-s) with
r = 1/p = (1 + 5)/2 and s = -p = (1 - 5)/2