Count the A's in a sequence We define a sequence of words as follows: Let $S_0=a$, and for $n≥1$, to obtain $S_n$, we replace each instance of $a, b,$ and $c$ in $S_{n−1}$ simultaneously with $ab, ac,$ and $a$, respectively. The first few words are then $S_1=ab, S_2=abac,$ and $S_3=abacaba$. Find the number of times $a $ appears in the first $1000$ letters of the word $S_{12}$. I haven't solved a question like thus. What should my approach be? Thanks.
 A: Let $A_n$ be the number of $a$'s, $B_n$ be the number of $b$'s and $C_n$ be the number of $c$'s in the word $S_n$. Then by the rules of constructing the words we get
\begin{align*}
A_n & = A_{n-1}+B_{n-1}+C_{n-1}\\
B_n & = A_{n-1}\\
C_n & = B_{n-1}.
\end{align*}
with $A_0=1, B_0=0$ and $C_0=0$. 
You can think of this as 
$$\mathbf{v}_{n}=\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}\mathbf{v}_{n-1},$$
where
$$\mathbf{v}_{n}=\begin{bmatrix}A_n\\B_n\\C_n\end{bmatrix}$$
Now if you can diagonalize this matrix then you can compute higher powers of it and make use of that to get $A_n,B_n,C_n$.
A: It’s always useful in problems like this to gather some data in order to get a feel for what’s going on. This is especially true here, since $12$ is fairly small.
Let $a_n,b_n$, and $c_n$ be the numbers of $a$s, $b$s, and $c$s, respectively, in $S_n$; $a_0=1$, and $b_0=c_0=0$. The replacement rules mean that
$$\begin{align*}
a_{n+1}&=a_n+b_n+c_n\\
b_{n+1}&=a_n\\
c_{n+1}&=b_n\;,
\end{align*}$$
from which we can quickly calculate the first $13$ values:
$$\begin{array}{c|ccc}
n&a_n&b_n&c_n\\ \hline
0&1&0&0\\
1&1&1&0\\
2&2&1&1\\
3&4&2&1\\
4&7&4&2\\
5&13&7&4\\
6&24&13&7\\
7&44&24&13\\
8&81&44&21\\
9&149&81&44\\
10&274&149&82\\
11&504&274&149\\
12&927&504&274
\end{array}$$
Unfortunately, $S_{12}$ is $1705$ characters long, so the problem is really to determine how many of those $927$ $a$s are in the first $1000$ characters. This requires that we look more closely at the actual strings $S_n$. Here are $S_0$ through $S_6$:
$$\begin{array}{c|l}
n&S_n\\ \hline
0&a\\
1&ab\\
2&abac\\
3&abacaba\\
4&abacabaabacab\\
5&abacabaabacababacabaabac\\
6&abacabaabacababacabaabacabacabaabacababacaba
\end{array}$$
It appears that each string repeats the previous one, followed by a new part. Here are the new parts:
$$\begin{array}{c|l}
n&\text{new}\\ \hline
0&\\
1&b\\
2&ac\\
3&aba\\
4&abacab\\
5&abacabaabac\\
6&abacabaabacababacaba
\end{array}$$
A close look suggests that for $n\ge 3$ the new part is simply the concatenated string $S_{n-2}S_{n-3}$, so that $S_n=S_{n-1}S_{n-2}S_{n-3}$. If that’s actually the case, the first $100$ characters of $S_{12}$ are the $927$ characters of $S_{11}$ together with the first $73$ characters of $S_{10}$. The first $73$ characters of $S_{10}$ are the same as the first $73$ characters of $S_9,S_8$, and $S_7$, which is $S_6S_5S_4$ (if our conjecture is correct), which makes it very straightforward to get the number of $a$s in those $73$ characters.
All that remains is to prove the conjecture that
$$S_n=S_{n-1}S_{n-2}S_{n-3}$$
for $n\ge 3$. Clearly a proof by induction is indicated, since the construction of the strings $S_n$ is recursive, and the proof itself turns out to be very straightforward — almost trivial.
