Discrete Math - Recursion

Question

When I read this question, I have no idea how to approach it. Can someone break down the steps to solving this question?

Let $Σ = \{a, b, c\}$. Find a recurrence for the number of length $n$ strings in $Σ^∗$ that do not contain any two consecutive $a$’s, $b$’s, nor c’s (i.e. none of $aa$, $bb$, nor $cc$ are in the string).

So this is what I have done so far: My Work

I have completed the problem and here is the solution: My Solution

THANK YOU to everyone who helped, or even looked at this post. Special kudos to @JMoravitz for his kind help!

Answer 1

You have three valid strings of length $1$. They are namely $a,b,c$. For each of these, there are two possible ways to continue them into a length $2$ string:

$$a \mapsto \begin{cases} ab\\ac\end{cases}$$

$$b\mapsto \begin{cases} ba\\bc\end{cases}$$

$$c\mapsto \begin{cases} ca\\cb\end{cases}$$

Now... for each of these six length two strings there are two ways to continue each into a length three string:

$$ab\mapsto\begin{cases}aba\\abc\end{cases}$$

$$ac\mapsto\begin{cases}aca\\acb\end{cases}$$

$$ba\mapsto\begin{cases}bab\\bac\end{cases}$$

$$\vdots$$

Notice, in the above process, there are no repeats. Convince yourself of this.

In general, given a valid length $n$ string, we may extend it in two ways to make a valid length $n+1$ string.

Convince yourself that every valid length $n+1$ string is uniquely comprised of a prefix made of a length $n$ string followed by suffix made of a single character which is different than the final character of the prefix.

Convince yourself then that supposing we know the number of valid length $n$ strings is $f(n)$, we can use this information and this information alone to calculate $f(n+1)$.

(There is one valid length $0$ string). There are three length $1$ strings. There are six length $2$ strings. There are twelve length $3$ strings, etc...

$~$

You are tasked with coming up with an equation for $f(n+1)$ which depends only on the value of $f(n)$ (or in some later problems it could also depend on $f(n-1),f(n-2),\dots$) and possibly some constants. Additionally, if you are tasked with it, you might be further asked to find a closed form for the function which avoids the necessity of referring to earlier values.