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_t 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₁? Why is N_{t + 1} = 2N_t for all t ≥ 1? Write down a simple formula for N_t for t ≥ 1.

(b) Suppose instead that dot requires 1 unit of time for transmission while dash requires 2 units. What are the values of N₁ and N₂? Justify the relation N_{t + 2} = N_t+1 + N_t for t ≥ 1. Hence write down a formula for N_t in terms of t.