# Prefix code with word lengths equal to consecutive Fibonacci numbers

Is it possible to find a prefix code with word lengths equal to consecutive Fibonacci numbers?

The sequence of Fibonacci numbers is: $$F_1=1,F_2=1,F_3=2,F_4=3,F_5=5,...$$

I think, I can use Kraft–McMillan inequality

" Let each source symbol from the alphabet

$$\displaystyle S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}$$ be encoded into a uniquely decodable code over an alphabet of size $$r$$ with codeword lengths

$$\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}.$$ Then

$$\displaystyle \sum _{i=1}^{n}r^{-\ell _{i}}\leqslant 1.$$ Conversely, for a given set of natural numbers

$$\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}$$ satisfying the above inequality, there exists a uniquely decodable code over an alphabet of size $$r$$ with those codeword lengths."

How can I proof Kraft–McMillan inequality for Fibonacci Numbers?

• For $r=2$ and $n>2$ this is false. For $r\geq3$ you could try some suitable bounds $\lambda_i\leq F_i$. Commented Jan 23, 2023 at 9:17

For $$r\geq 3$$ and arbitrary integer $$n>0$$ the Kraft–McMillan inequality for Fibonacci Numbers is satisfied:
Let $$n\geq 3$$. Then it is easy to show by induction that $$F_n\geq n-1$$. Therefore $$\sum_{i=1}^n r^{-F_i}\leq \frac2r+\sum_{i=3}^n r^{-(i-1)}\leq \frac23+\sum_{i=3}^\infty 3^{-(i-1)}=\frac23+\frac1{3^{2}}(1+\frac13+\frac1{3^2}+\ldots)\\=\frac23+\frac1{3^2}\frac1{1-\frac13}=\frac23+\frac1{3^2}\frac32=\frac23+\frac16=\frac56<1.$$