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?

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