A topic from information theory: imagine an information transmission system
that uses an alphabet consisting of just two symbols 'dot' and 'dash', say.
Messages are transmitted by first encoding them into a string of these
symbols, and no other symbols (say blank spaces) are allowed. Each symbol
requires some length of time for its transmission. Therefore, for a fixed
total time duration only a finite number of different, message strings are
possible. Let \(N_{1}\) denote the number of different message strings possible
in \(t\) time units.
(a) Suppose that dot and dash each require one time unit for transmission.
What is the value of \(N_{1} ?\) Why is \(N_{t+1}=2 N_{1}\) for all \(t \geqslant
1\) ? Write down a simple formula for \(N_{t}\) for \(t \geqslant 1\).
(b) Suppose instead that dot requires 1 unit of time for transmission while
dash requires 2 units. What are the values of \(N_{1}\) and \(N_{2}\) ? Justify
the relation \(N_{t+2}=N_{t+1}+N_{i}\) for \(t \geqslant 1 .\) Hence write down a
formula for \(N_{t}\) in terms of \(t\).
(Hint: The general solution of Fibonacci recurrence, is given in Example
7.18.)