Count strings of size 21 over the letters $\{A, C, G, T \}$ where an $A$ is always followed by a $C$ The question asks how many strings can we get if it is selected from {A,C,G,T}, and there always has an A followed by a C
Here is my solution: 
$$C(11,10)\cdot 3 + C(12,9)\cdot 3^3 + C(13,8)\cdot 3^5+\cdots+C(20,1)\cdot 3^{19}+ C(21,0)\cdot 3^{21}$$
Where in $C(n,k)\cdot 3^{n-k}$, $n$ is the numbers of overall if we consider A and C together, k is the number of A's in the string, and we have 3 choices (C,G,T) for other positions in the string.
Am I right?
 A: The generating function approach is that you are seeking the coefficient of $x^{21}$ in the expansion of:
$$\sum_{n=0}^{\infty} \left(x^2+3x\right)^n = \frac{1}{1-3x-x^2}$$
For every $n$, you get that you want the coefficient of $x^{21-n}$ in $(x+3)^n$, which  is $\binom{n}{21-n}3^{2n-21}$. Since we need $0\leq 21-n\leq n$, you restrict yourself to terms $11\leq n\leq 21$ and we get your sum:
$$\sum_{n=11}^{21}\binom{n}{21-n}3^{2n-21}$$
From the power series, you can use partial fractions and get that the $n$th coefficient is the nearest integer to:
$$\frac{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}}{\sqrt{13}}$$
Which for $n=21$ gives $72171863277$ in my calculator.
This is also twice the coefficient of $\sqrt{13}$ in the expansion of $\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}$, which is:
$$\frac{1}{2^{n}}\sum_{k=0}^{\lfloor n/2\rfloor}\binom {n+1}{2k+1}13^k3^{n-2k}$$
This gives a basic checksum, since it means that modulo $13$, the value is congruent to $(n+1)\cdot 2^{3n}$. For $n=21$. So when $n=21$ this is $22\cdot 2^{63}\equiv 9\cdot 8\equiv 7\pmod{13}$, and this is true for our value.
You can also compute the lower right value of the matrix:
$$\begin{pmatrix}0&1\\1&3\end{pmatrix}^{21}$$
which Wolfram Alpha also gives as $72171863277.$ Computing this exponentiation can be done somewhat efficiently using the method of repeated square.
A: Yes, I think you are right. The number of strings of size $n$ with $k$ copies of $A$ (followed by $G$) with $2k\leq n$, is $\binom{n-k}{k}3^{n-2k}$. Hence the total number of such strings of size $n$ is
$$a_n:=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}3^{n-2k}.$$
Note that for $n\geq 3$, $a_n = 3a_{n-1} + a_{n-2}$ with $a_1=3$ and $a_2=10$. The final result should be $a_{21}=72171863277$ (see OEIS A006190).
A: Let $f(n)$ denote the number of strings of length $n$ such that $A$ is always followed by a $C$.  
Now, let's make the following observation: to begin constructing a string of length $n \geq 3$, we can either begin with a C,G, or T, following by a string of length $n-1$, or we can begin with an "AC", followed by a string of length $n-2$.   In other words, we can conclude that
$$
f(n) = 3 \cdot f(n-1) + f(n-2)
$$
I think this observation makes for a more elegant approach.  In particular, we are now simply solving a linear recurrence with constant coefficients.
In fact, if we define $f(0) = 1$ (since there is one "empty string" of length $0$), then the relation above applies for $n \geq 2$.
