The Fibonacci Sequence

[Nanuq]

I was discussing a joke on a math forum, and stumbled across the most perfect explanation I have ever seen for the Fibonacci sequence. In case anybody has been losing sleep over it?

Okay, whatever. Here it is. Prepare to be awestruck and amazed!

Consider two glass plates against each other. We send in a ray of

light from above. This ray of light can be reflected several times

within the plates before it gets out, like this:

.\................/...............

..\../\........../

...\/..\......../.................

........\../\../

.........\/..\/...................

This ray of light has been reflected 5 times before getting out.

We will consider the sequence of numbers of routes r(n) with n

reflections. Of course r(0) = 1, that is, the ray of light can go

through with no reflections in one way.

Now let us count the number of possible routes that a ray of light can

take inside these glass plates with one reflection:

.\..../...\......../..............

..\../.....\....../

...\/.......\..../................

.............\../

..............\/..................

There are 2 possible routes with 1 reflection, so r(1) = 2.

Two reflections:

.\.........\........\.............

..\../\.....\........\....../\

...\/..\.....\........\..../..\...

........\.....\../\....\../....\

.........\.....\/..\....\/......\.

..........\.........\............\

There are 3 possible routes with 2 reflections, so r(2) = 3.

Three reflections:

.\......../.\............/..\............/...

..\../\../...\../\....../....\....../\../

...\/..\/.....\/..\..../......\..../..\/.....

...................\../........\../

....................\/..........\/...........

.\................/...\............/...

..\....../\....../.....\........../

...\..../..\..../.......\......../.....

....\../....\../.........\../\../

.....\/......\/...........\/..\/.......

There are 5 possible routes with 3 reflections, so r(3) = 5.

The sequence we find is 1, 2, 3, 5,.... How do we show that this is

indeed the Fibonacci sequence, and goes on 8, 13, 21,... etc.?

Suppose we want to know the number of routes with n reflections, and

we do know r(n-1) and r(n-2).

Suppose that for n reflections the ray of light should leave the glass

plates downwards.

We know there are r(n-2) routes such that the ray of light leaves

downwards with n-2 reflections. These routes can be extended with a

route via the middle line, and then they form all possible routes with

n reflections and the last reflection in the middle line.

We also know there are r(n-1) routes, so that the ray of light leaves

upwards with n-1 relfections. If these are reflected back downwards,

then they form all possible routes with n reflections with the last

reflection in the top line.

That gives that the total of possible routes with n reflections

r(n) = r(n-2)+r(n-1). This is exactly Fibonacci's formula.