Suppose there are {1,2,3} in a set. How many n digit numbers can you form such that there are no adjacent 1s.
I tried randomly and tried to induce. I do not know how far I am correct.
For n=2, it is $2^3$, for n=3, it is $2^4$ and ... Well, making induction by applying brute force might not the perfect way. I want suggestions as to how to tackle these kind of problems.
$\textbf{Added}$: My induction seems mistaken any way. I would appreciate solutions.