Awesome q2a theme
0 votes
28 views

Messagees are transmitted over a communication channel using two signals. the transmission of one signal requires 1 microsecond and the transmission of the other requires two microseconds. the recurrence relation for the numver of different massages 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>=2) is 

  1. $a_{n} = a_{n-1} + a_{n-2}$
  2. $a_{n} = a_{n-1} + 2a_{n-2}$
  3. $a_{n} = 2a_{n-1} + a_{n-2}$
  4. $a_{n} = a_{n-1} + a_{n-3}$
in Mathematical Logic by (5 points) | 28 views

1 Answer

+3 votes

$a_n$ is the number of different messages that can be sent in exactly $n$ microseconds.

$\implies a_{n-1}=$ number of different messages that can be sent in $n-1$ microseconds,

and $a_{n-2}=$ number of different messages that can be sent in $n-2$ microseconds.

For the $n^{th}$ microsecond:

If the last signal is of $1$ microsecond:

Let the messages possible in this case be $end_1$. Now, in this case you can merge last signal with any message that was possible in $n-1$ microseconds, hence you can have $a_{n-1}$ different messages which will have last signal of $1$ microsecond. 

$\therefore end_1=a_{n-1}$

 

If the last signal is of $2$ microseconds:

Let the messages possible in this case be $end_2$. In this case you can merge last signal with any message that was possible in $n-2$ microseconds, hence you can have $a_{n-2}$ different messages which will have last signal of $2$ microseconds.

$\therefore end_2=a_{n-2}$

 

Since the last signal can be of either $1$ microsecond or $2$ microsecond, the total number of different messages that can be sent in $n$ microseconds , i.e. $a_n$ will be:

$end_1 + end_2$

$=a_{n-1}+a_{n-2}$

 

Hence, option $1.\ a_n=a_{n-1}+a_{n-2}$ is correct.

 

by (855 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,437 questions
2,714 answers
13,238 comments
95,460 users