Suppose we have to ascent a flight of stairs and can take only one or two steps at a time. How many different patterns of ascent are there? We start with the simplest cases. With one step there is only one way; with two, there are two: take two single steps or one double step. With three steps, there are three possibilities. We can now proceed in an inductive manner.

Suppose there are patterns for steps and patterns for steps. Now suppose we have a flight of steps. There are only two ways to arrive at step : a single step from step or a double step from step . Therefore, the number of patterns is given by the recurrence relation

This is precisely the relationship that defines the *Fibonacci numbers *: each number is the sum of the previous two. The sequence of patterns is the well-known sequence

which is found in a multitude of different contexts.

**Patterns in Sanskrit Poetry**

Fibonacci (c.1175–1250) was an Italian mathematician who introduced the Hindu-Arabic number system to Europe. He is remembered today mainly for the sequence that bears his name. But this sequence had been studied centuries earlier. Virahanka, who lived some time between AD 600 and 800, was an Indian mathematician known for his analysis of the structures and patterns of Sanskrit poetry. He studied poetic forms in which the language is broken into short and long syllables, a long syllable having two metric units and a short one having one unit. He found the number of patterns of long and short syllables for a given overall length. For example, with a five-unit line, there are eight possibilities, as shown in the Table above (*S* denotes a short syllable and *L* a long one). The similarity of this problem to the stair-climbing one is clear: the two problems lead to the same sequence.

**Musical Rhythms**

The rhythmic patterns of musical composition also give rise to the Fibonacci sequence. We consider all the possible rhythms in a single bar in common time (four beats to the bar). We use only crotchets (quarter notes) and minims (half notes), and count a crotchet as one unit and a minim as two. Then the five possible patterns are:

Once again, we are making up the fixed number of beats in a bar from components of one and two units. Therefore, the number of rhythms in a bar with beats is the -th Fibonacci number.

**The Morse Code**

Letters are represented in Morse code by long and short sounds, usually called dots and dashes. A dash should equal three dots in length. To ensure a good separation, we represent a dot by one unit of time with sound for the first half and silence for the second. A dash is then represented by two time units with sound for the first three half-units and silence for the last half-unit. Thus, a dot is one time unit and a dash is two:

Now we consider the possible patterns for letters of time units. The Table below shows all the alphabetical and numerical characters with code lengths between one and ten units. We see that the most frequently occurring letters have shorter codes. All the patterns of five or fewer units are employed. Many of the longer patterns are not used (some of these are employed for punctuation characters, etc.). The sequence of Fibonacci numbers is again in evidence in the number of patterns.

==================

For reference, the dot-dash patterns of the Morse Code are shown below.