Say I have three objects: Object A, B, and C. I may not choose object B two times in a row. How many choices would there be for n = 2? n=3?
My goal is to find a recurrence relation for this, but I am struggling to understand how this would even work mathematically.
On
Call a string good if it does not contain the substring $BB$, and let $g_n$ be the number of good strings of length $n$. How many good strings of length $n+1$ can be made from a good string of length $n$? As you’ve realized, it depends on whether the string of length $n$ ends in $B$, so let’s keep track of those separately: let $b_n$ be the number of good strings of length $n$ that end in $B$, and let $a_n$ be the number of good strings of length $n$ that do not end in $B$. Clearly $a_n+b_n=g_n$.
Suppose that $s$ is a good string of length $n$. No matter what letter is at the end of $s$, we can add an $A$ or a $C$ to get a good string of length $n+1$, and if $s$ does not end in $B$, we can also add a $B$. Thus, we get $2g_n$ good strings of length $n+1$ that end in $A$ or $C$, and $a_n$ good strings of length $n+1$ that end in $B$, so $a_{n+1}=2g_n$, $b_{n+1}=a_n$, and $g_{n+1}=2g_n+a_n$.
We’re getting there, but we still have to figure out how to get rid of that $a_n$ term. In this case that turns out to be pretty easy: we discovered that $a_{n+1}=2g_n$, which immediately tells us that $a_n=2g_{n-1}$ and hence that $g_{n+1}=2g_n+2g_{n-1}$ or, if you prefer, that $g_{n+1}=2(g_n+g_{n-1})$.
Let $w_n$ denote the number of ways of choosing the objects $n$ times, so that the last chosen object (object chosen the $n^{th}$ time) is not $B$. Then we cab derive the following recurrence relation for $w_n$:
$$w_n=2(w_{n-1}+w_{n-2})$$ This is because in the $n^{th}$ round either $A$ or $C$ has to be chosen, according to our defintion of $w_n$ and there are two options upto the $(n-1)^{th}$ round: