0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .