## Information on Fibonacci Sequences

A *Fibonacci sequence* is a recursive sequence which has starting
values F_{0} = 1 and F_{1} = 1,
and
recursive formula F_{n} = F_{n - 1} + F_{n -
2}. It is usually represented by a 0-1
string where the substring 11 cannot occur. This is the first
representation given by COS. The second representation we call the
Stair-Stepping representation. Each of the outputs in the second
representation corresponds to a series of 1 or 2 steps taken on n +
1 stairs. The third representation in COS gives Reflection
diagrams which represent the different ways in which a beam of light can
reflect through two panes of glass placed back to back. A reflection may
occur at
the edge of the glass, or it may occur where the panes meet, but the beam
cannot reflect where the panes meet twice in a row. Thus, this
corresponds to the 0-1 strings.
COS can generate Fibonacci sequences in either lexicographic(lex)
order or
in a Gray Code order. To generate in lex order, input a value for n and
none for k. To generate in a Gray Code order, input a value for n and a
nonzero value for k.

The algorithm used by COS is a recursive backtracking algorithm.

It was last updated .