Question

Messages are transmitted over a communication channel using two signals. The transmission of one signal requires 1 microsecond and the transmission of the other signal requires two microseconds. The recurrence relation for the number of different messages consisting of sequences of these two signals (where each signal is immediate followed by the next signal) that can be send in n microseconds $(n\le 2)$ is

• A. $a_n=a_{n-1}+a_{n-2}$
• B. $a_n=2a_{n-1}+a_{n-2}$
• C. $a_n=a_{n-1}+a_{n-3}$
• D. $a_n=a_{n-1}+2a_{n-2}$

Answer 1

The correct option is A $a_n=a_{n-1}+a_{n-2}$

option (a)

Let $a_n=$ number of different messages that can be sent in n microseconds.

Case (i) : If the first signal required one microsecond, then the remaining part of the message can be sent in $a_{n-1}$ ways.

Case (ii) : If the first signal require 2 microseconds, then the remaining part of the message can be sent in $a_{n-2}$ ways.

These two cases are mutually exclusive and exhaustive.

$\therefore$ By sum rule, the recurrence relation is
$a_n=a_{n-1}+a_{n-2}$.