Proof that $\sum_{i=0}^{\infty}2^{(-i+1)} < \sum_{i=1}^{\infty}2^{-(i+1)} \cdot F_i $

Question

I am Facing a problem when learning about data compression. I learned that the Fibonacci code for data compression is complete it means it can be represented as complete node tree. I am trying to prove it using a hint from my professor to use Kraft-McMillan equality.

from Kraft-McMillan equality I get that Kraft of Fib Code is

$ S = \sum_{i=1}^{\infty}2^{-(i+1)}\cdot F_i $

where $ F_i $ is the Fibonacci number indexed i

I need help to manipulate S so that the claim follows

$\sum_{i=0}^{\infty}2^{(-i+1)} < S $

---

I tried multiplying by 2 and looking from diffrent angles all the basic tricks i use to know back in the days but couldnt manipulate S to proof the claim if you have some insight please let me know!

---

thanks in advance for your help!

Answer 1

I don't know if the $F_i$ in exponent (but if, then it's easy to show, since $F_i \ge 1$).

Otherwise let's use Binet's formula.

$$ S = \dfrac{1}{2}\sum_{i \ge 0} \frac{F_i}{2^i} = \dfrac{1}{4}\sum_{i \ge 0} \frac{\phi^i - \psi^i}{2^i} = \dfrac{1}{4} \left(\dfrac{2}{2 - \phi} - \dfrac{2}{2 - \psi}\right) = \dfrac{\sqrt{5}}{2} > 1 = 2 \times\sum_{i \ge 0} 2^{-(i + 1)} $$