A message is transmitted by a series of signals from the following 19 signals: s1, s2, ... , S19.
Knowing that the signal s1 take 1 second, signal s2 to s11 take 2 seconds each and the other signals take 3 seconds. an is the number of messages possibles that take n seconds to be transmitted, where n ≥ 1.
a) Calculate a1, a2 and a3
I found that:
a1 = 1 (1 message of 1 second)
a2 = 11 (1 message of 2 times 1 second and 10 messages of 2 seconds because there is 10 different 2 seconds signals)
a3 = 29 (with the same logic)
b) Determine the recurrence relation for n >=4. Justify.
Hint from the teacher: |An| = |Bn| + |Cn| + |Dn|
I have a clue that it will look like a homogenous linear relation:
an = C1 x an-1 + C2 x an-2 + C3 x an-3
And I think C1 = 1, C2 = 10 and C3 = 8 but I need to prove it with my teacher's clue.
Thus I have : an = an-1 + 10an-2 + 8an-3
Here's an example with my teacher's method apply to bit string that must have at least two consecutive zeros:
Bn = {(1, a2, ..., an : ∀i, ai ∈ {0,1}, aj = aj+1 = 0}
Cn = {(0, 1, a3, ..., an : ∀i, ai ∈ {0,1}, aj = aj+1 = 0}
Dn = {(0,0, a3, ..., an : ∀i, ai ∈ {0,1}, aj = aj+1 = 0}
An = Bn ∪ Cn ∪ Dn
Bn ∩ Cn = ∅
Bn ∩ Dn = ∅
Cn ∩ Dn = ∅
gives an = an-1 + an-2 + $2^{n-2}$
(for 1 at the beginning for n-1, 2 at the beginning for n-2 and 2 times the same for $2^{n-2}$)
Thank you for your help!
Let $n\ge 4$. Any $n$-second message ends in (i) $s_1$; or (ii) one of the $10$ two-second thingies, or (iii) one of the $8$ three-second thingies.
There are $a_{n-1}$ $n$-second messages of Type (i). For every one of the $a_{n-1}$ $(n-1)$-second messages can be extended to a Type (i) $n$-second message in exactly $1$ way, by appending $s_1$.
There are $10a_{n-2}$ Type (ii) $n$-second messages. For every one of the $a_{n-2}$ $(n-2)$-second messages can be extended to a Type (ii) $n$-second message by appending any of the $10$ symbols $s_2$ up to $s_{11}$.
Similarly, there are $8a_{n-3}$ $n$-second messages of Type (iii). Thus $$a_n=a_{n-1}+10a_{n-2}+8a_{n-3}.$$
Added: If we want to be very set theoretical in our language, we can let $A_n$ be the set of $n$-second messages, $B_n$ the set of $n$-second messages with last signal $s_1$, $C_n$ the set of $n$-second messages with last signal one of $s_2$ to $s_{11}$, and $D_n$ be the set of $n$-second messages with last signal one of $s_{12}$ to $s_{19}$. (Or else we classify by first signal instead of last, doesn't matter as long as we are consistent.)
Then $a_n=|A_n|$. But $A_n=B_n\cup C_n\cup D_n$, and $B_n$, $C_n$, and $D_n$ are pairwise disjoint. That is, $B_n\cap C_n=\emptyset$, $\dots$.
It follows that $$a_n=|A_n|=|B_n|+|C_n|+|D_n|.\tag{1}$$ Now we obtain expressions for $|B_n|$, $|C_n|$, $|D_n|$. We will only deal with $|C_n|$.
An elements of $C_n$ has a unique representation as an element of $A_{n-2}$, with one of $s_2,\dots,s_{11}$ appended. Thus by the Multiplication Principle, $|C_n|$ is equal to $|A_{n-2}|$ times the cardinality of the set $\{s_2,\dots,s_{11}\}$. More briefly, $|C_n|=(a_{n-2})(10)=10a_{n-2}$.
Now you can deal similarly with the other two, substitute in Equation (1) to get the recurrence.`