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 F_{N+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 F_{n}. Recall also that, by the definition of the
Fibonacci numbers, F_{0}=0 and F_{1}=1, and that
F_{n} = F_{n-2} + F_{n-1}. Thus the next
two Fibonacci numbers are F_{2}=1 and F_{3}=2.
Again, we wish to prove that:

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

N = 1 case: F_{N+1}-1 = F_{1+1}-1
= F_{2}-1 = 1-1 = 0

- There is only one code of length one cell, the code
"1". Because it has a "1" in the cell weighted
F

N = 2 case: F_{N+1}-1 = F_{2+1}-1
= F_{3}-1 = 2-1 = 1

- There are only two codes of length two cells, the
codes "0" and "11".

__The code "0"__: The code "0"
generates the value zero.

__The code "11"__: Because it has a "1" in the
F_{0}=0 cell and a "1" in the F_{1}=1
cell, the value of the code "11" is 1.

Hence: the set
of codes of length 2 cells generates values from zero through
F_{N+1}-1 = 1, Q.E.D. for the N=2 case.

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

- Recall that in an inductive proof, we are now allowed
to

a) N-cell codes with a "0" in cell N-1
(the furthest-right cell) must also have a "0" in cell
N-2, because "0" is two cells wide. This "0"
contributes nothing to the value. Therefore, the values of these
codes are the values generated by all codes of length N-2. By
the induction hypothesis, these values range from zero through
F_{(N-2)+1}-1 = F_{N-1}-1.

b) N-cell codes with a "1" in cell N-1
contain a code of length N-1 to the left of that "1".
By the induction hypothesis, these values range from zero through
F_{(N-1)+1}-1 = F_{N}-1. However, the "1"
in cell N-1 contributes a weight of F_{N-1} to these values,
so the overall value ranges from F_{N-1} through (F_{N}-1
+ F_{N-1}).

Therefore, combining cases a) and b), the N-cell
codes cover values from zero through (F_{N}-1 + F_{N-1})
= (F_{N-1} + F_{N} - 1) = ( (F_{N-1} +
F_{N}) - 1). But by the basic definition of the Fibonacci
numbers, (F_{N-1} + F_{N}) = F_{N+1}.
Therefore,

The set of codes of length N cells generates values
from zero through F_{N+1}-1, Q.E.D.

Click here to return to the starting Fibonacci Code page

Click here to return to Larry Krakauer's home page