Find a recurrence relation for the number of strings in $\left \{ 0,1,2\right \}^{n}$ that do not contain any repeated character. (So, no 00, 11, or 22.)
I found a similar question here, but this seems a opposite question as mine. what's the beginning step to find out the recurrence relation, they are too many possible answers, I don't know how to get start.
Look at the last character of a string of length $n-1$ and note that there are two valid characters that extend it. So $f(n) = 2f(n-1)$.
Obviously $f(1) = 3$ is the base case, giving $f(n) = 3 \cdot 2^{n-1} $.