# Number of words of length n which contain the sequence (aa) at least once

Let $A = {a,b,c}$ be the alphabet to use for the words. Number words of length n which contain the sequence $(aa)$ at least once.

$n = 0$ and $n = 1$ yield no words, because they do not contain $(aa)$. So we can start with $n = 2$

There are $n-1$ possibilities for the position of the $aa$. We have $n-2$ remaining letters, for which each has three possibilities for a letter.

I come to the conclusion that the formula must be $(n-1) \cdot 3^{n-2}$

I'm not sure about this and I wonder if there is a cleaner approach, maybe a recurvive approach?

• The $3(n-2)$ part should be $3^{n-2}$ – turkeyhundt Jan 19 '15 at 9:05
• Your approach would count $aabaa$ twice, and $aaaaa$ four times, and therefore give you the wrong answer for $n=5$. – Arthur Jan 19 '15 at 9:15
• But I don't think it's as simple as that formula because it would count, say, $aaa$ multiple times. – turkeyhundt Jan 19 '15 at 9:15
• thank you for your comments, I've altered the formula :) – warg Jan 19 '15 at 10:08

Hint:

Denote the number of words of length $n$ that do not contain sequence $aa$ by $p_{n}$ and split up:$$p_{n}=q_{n}+r_{n}$$ Here $q_{n}$ stands for words of length $n$ that do not contain $aa$ and have $a$ as first letter and $r_{n}$ stands for words of length $n$ that do not contain $aa$ and do not have $a$ as first letter.

Then we have the recursion relations: $$r_{n+1}=2p_{n}\text{ and }q_{n+1}=r_{n}$$ There are $3^{n}$ words of length $n$ so you are actually looking for $3^{n}-p_{n}$.

• thanks, this helped a ton. – warg Jan 19 '15 at 10:08
• Glad I could help. You are very welcome. – drhab Jan 19 '15 at 10:14