Question

How many different messages can be transmitted in n microseconds using three different signals if one signal requires 1 microsecond for transmittal, the other two signals require 2 microseconds each for transmittal, and a signal in a message is followed immediately by the next signal?

Answer 1

Answer:

a_{n} = 2/3 . 2^n + 1/3 . (-1)^n

Explanation:

Let a_{n} represents number of the message that can transmitted in n microsecond using three of different signals.

One signal requires one microsecond for transmittal: a_{n}-1

Another signal requires two microseconds for transmittal: a_{n}-2

The last signal requires two microseconds for transmittal: a_{n}-2

a_{n}= a_{n-1} + a_{n-2} + a_{n-2} = a_{n-1} + 2a_{n-2}, n ≥  2

In 0 microseconds. exactly 1 message can be sent: the empty message.

a_{0}= 1

In 1 microsecond. exactly 1 message can be sent (using the one signal of one  microseconds:

a_{0}= 1

2- Roots Characteristic equation

Let a_{n} = r^2, a_{n-1}=r and a_{n-2}= 1

r^2 = r+2

r^2 - r - 2 =0                 Subtract r+6 from each side

(r - 2)(n+1)=0                  Factorize

r - 2 = 0 or r +1 = 0       Zero product property

r = 2 or r = -1                 Solve each equation

Solution recurrence relation

The solution of the recurrence relation is then of the form a_{1} = a_{1 r^n 1} + a_{2 r^n 2} with r_{1} and r_{2} the roots of the characteristic equation.

a_{n} =a_{1} . 2^n + a_{2}.(-1)"

Initial conditions :

1 = a_{0} = a_{1} + a_{2}

1 = a_{1} = 2a_{1} - a_{2}

Add the previous two equations

2 = 3a_{1}

2/3 = a_{1}

Determine a_{2} from 1 = a_{1} + a_{2} and a_{1} = 2/3

a_{2} = 1 - a_{1} = 1 - 2 / 3 = 1/3

Thus, the solution of recursion relation is a_{n} = 2/3 . 2^n + 1/3 . (-1)^n