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 and F₁=1, and that F_n = F_n-2 + F_n-1. Thus the next two Fibonacci numbers are F₂=1 and F₃=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 = F₂-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₀=0, its value is 0. Hence: the set of codes of length 1 generates values from zero through F_N+1-1 = 0, Q.E.D. for the N=1 case.

N = 2 case: F_N+1-1 = F₂₊₁-1 = F₃-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 cell and a "1" in the F₁=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 assume the "induction hypothesis" to be true for the cases N-1 and N-2. Then:


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 Larry Krakauer's home page