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 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 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
The code "0": The code "0" generates the value zero.
The code "11": Because it has a "1" in the F0=0 cell and a "1" in the F1=1 cell, the value of the code "11" is 1.
Hence: the set
of codes of length 2 cells generates values from zero through
FN+1-1 = 1, Q.E.D. for the N=2 case.
Induction step (the general case for codes of length
N, N > 2):
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 = FN-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 = FN-1. However, the "1"
in cell N-1 contributes a weight of FN-1 to these values,
so the overall value ranges from FN-1 through (FN-1
Therefore, combining cases a) and b), the N-cell
codes cover values from zero through (FN-1 + FN-1)
= (FN-1 + FN - 1) = ( (FN-1 +
FN) - 1). But by the basic definition of the Fibonacci
numbers, (FN-1 + FN) = FN+1.
The set of codes of length N cells generates values from zero through FN+1-1, Q.E.D.
Click here to return to Larry Krakauer's home page