Mathematical Proof of Conversion Correctness

Although the assignment of value to the Fibonacci codes seems quite evident from the method used to generate and count the codes, a rigorous proof is a bit lengthy.

We wish to prove that with Fibonacci weights assigned to the cells, the set of Fibonacci codes of length N cells converts to integer values from zero through FN+1-1.

We will number the cells of an N-cell code from 0 through N-1, and recall that a "0" element uses two cells, and a "1" element only a single cell. The value of a code is equal to the sum of the weights of the cells that contain a "1", where the cells are weighted such that cell n has weight Fn. Recall also that, by the definition of the Fibonacci numbers, F0=0 and F1=1, and that Fn = Fn-2 + Fn-1. Thus the next two Fibonacci numbers are F2=1 and F3=2. Again, we wish to prove that:

The set of codes of length N cells (N > 0) generates values from zero through FN+1-1

The simplest proof is by induction. Because the Fibonacci number definition "reaches back" two steps, we need two "base" cases:

N = 1 case: FN+1-1 = F1+1-1 = F2-1 = 1-1 = 0

N = 2 case: FN+1-1 = F2+1-1 = F3-1 = 2-1 = 1

Induction step (the general case for codes of length N, N > 2):

Click here to return to the starting Fibonacci Code page

Click here to return to Larry Krakauer's home page