Lesson 3

The initial vector is \[\begin{pmatrix}a_1&b_1\end{pmatrix}=\begin{pmatrix}1&1\end{pmatrix}.\] Therefore, if \[A= \begin{pmatrix}1&1\\ 1&0\end{pmatrix},\] then \[\begin{pmatrix}a_n&b_n\end{pmatrix} = \begin{pmatrix}1&1\end{pmatrix}A^{n-1}.\] So, the total number of strings is \(N(n)=a_{n}+b_{n}\).

You can note that Fibonacci numbers appear here. Since \(b_{n+1}=a_{n}\), we have \[N(n+1)=a_{n+1}+b_{n+1}=(a_{n}+b_{n})+a_{n}=N(n)+N(n-1).\] The initial values are \(N(1)=2\) and \(N(2)=3\), so \[N(n)=F(n+2).\] In particular, for \(n=10\) the answer is \(F(12)=144\).