Motivation: The following is a problem I encountered some time ago and it bothers me since I did not solve it as expected. My original way to solve it was using calculus, however, I was expected to solve it with information theory knowledge. I also provide what I think was the intention of the author. However, I am not sure how to execute this "plan".
Question: Let $C$ be some code with $T_i$ codewords of length $i$, where $T_i$ satisfies the following recurrence relation:
- $T_5=2,T_4=T_3=1$.
- $T_{n+1}=T_n+T_{n-1}+T_{n-2}$
We need to show that $$ K(C):=\sum_{c\in C} 2^{-|c|}=\sum_{i=1}^{\infty}T_i\cdot 2^i=1$$ The first equality was an instruction, and the second was the claim to be shown. The solution should use methods from information theory and data compression.
I guess we needed to show that the code is complete, i.e., every node in the tree has $0$ or $2$ children, and then by Kraft's inequality $K(C)=1$.
Discrete Math Version. Consider a tree, where the number of leaves at depth $i-1$ is $T_i$. We need to show that every node in the tree has $0$ or $2$ children.