Consecutive ones (Recurrence)

Question

I am studying for my exam and this is an example I don't understand:

Consider all words in $\{1,2,3\}$ with n characters. We know from combinatorics that there are $3^n$ different words. Question: How many words have at least two consecutive ones?

The recurrence relation is: $A_{n+3} = 3A_{n+2} - 2A_n + 2 \times 3^n$. Can somebody explain this recurrence relation?

Is the edit right ... $A_{n+3} = 3A_{n+2} - 2A_{\color{red}{n+1}} + 2 \times 3^n$ would seem more plausible. — Donald Splutterwit, Jun 05 '17 at 19:52
@Anonymous Have you tried coming up with a recurrence relation yourself and seeing how it compares with the given answer? — user12345, Jun 05 '17 at 20:03
Write it as $A_{n+3} = 3\cdot A_{n+2} + 2\cdot(3^n - A_n)$. Perhaps it's easier to understand with the right grouping. — Daniel Fischer, Jun 05 '17 at 20:09

score 1 · Answer 1 · answered Jun 05 '17 at 20:11

Let's say a word has property P if it has at least two consecutive ones (I don't want to keep repeating this long sentence). I will also call a word of length $n$ an $n$-word.

The number of $n$-words with property P is denoted by $A_n$. Now let me break $A_{n+3}$ into $B_1+B_2+B_3$, where $B_i$ is the number of $(n+3)$-words with property P such that the first letter is $i$. But then $B_2=B_3=A_{n+2}$ since by removing the first letter we are left with a $(n+2)$-word with property P. So until now $$ A_{n+3}=2A_{n+2}+B_1 $$ Now we need understand what $B_1$ is. Let's further break $B_1$ into $B_1=C_1+C_2+C_3$ where $C_j$ is the number of $(n+3)$-words with the first letter 1, and second letter $j$. Again one sees that $C_2=C_3=A_{n+1}$ since a 12 or 13 can be removed without any consequence. Hence $$ A_{n+3}=2A_{n+2}+2A_{n+1}+C_1 $$ On the other hand $C_1=3^{n+1}$ since the consecutive ones has already happened. In other words $$ A_{n+3}=2A_{n+2}+2A_{n+1}+3^{n+1} $$ Using the same relation for $n+2$ we get $$ \begin{cases} A_{n+3}=2A_{n+2}+2A_{n+1}+3\times 3^{n}\\ A_{n+2}=2A_{n+1}+2A_{n}+3^{n} \end{cases} \Longrightarrow A_{n+3}=3A_{n+2}-2A_n + 2\times 3^n $$ where in the last step I am subtracting the two equations.

score 1 · Accepted Answer · answered Jun 05 '17 at 20:13

An acceptable string of $n+3$ digits can either come from adding a digit to an acceptable string of $n+2$ digits or from an unacceptable string of $n$ digits to which we append a $2$ or $3$ and then two $1$s. The last two $1$s make the string acceptable and the $2$ or $3$ before makes sure we don't have two $1$s in the $n+2$ digit string. Appending a digit to an $n+2$ digit string can happen in $3A_{n+2}$ ways. The number of unacceptable $n$ digit strings is $3^n-A_n$, there are two ways to choose the $n+1$st digit, so the total is $3A_{n+2}+2(3^n-A_n)$

Consecutive ones (Recurrence)

2 Answers2