Question: Suppose we have a satellite in orbit. To communicate to the satellite, we can send messages composed of two signals: dot and dash. Dot takes 2 microseconds to send, and dash takes 3 microseconds to send. Imagine that we want to know the number of different messages, M(k), that can be sent in k microseconds.
- If k is 0 or 1, we can send 1 message (the empty message)
- If k is 2 or 3, we can send 1 message (dot or dash, respectively)
- If k is larger than 3, we know that the message can start with either dot or dash. If the message starts with dot, the number of possible messages is M(k - 2). If the message starts with dash, the number of possible messages is M(k - 3). Therefore the number of messages that can be sent in k microseconds is M(k - 2) + M(k - 3).