No of n-digit numbers with no adjacent 1s. 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.
 A: Let $f_n$ be the number of allowed $n$-digit numbers with a $1$ at the right and $g_n$ be the number without a $1$ at the right.  Then you have $$f_{n+1} = g_n$$ $$g_{n+1}=2f_n+2g_n$$ starting with $f_1=1$ and $g_1=2$ (or $f_0=0, g_0=1$).  
You want $$h_n  = f_n + g_n = g_{n-1}+g_{n} = 2h_{n-2}+2h_{n-1}$$ which you can solve starting at $h_0=1,h_1=3$ or look up at OEIS A028859
A: Let $a_n$ be the count of such numbers ending in $1$ and $b_n$ the count of such numbers not ending in $1$.
Then we have the recursion 
$$a_{n+1}=b_n\qquad b_{n+1}=2(a_n+b_n)$$
with initial conditions $a_1=1, b_1=2$ and actually are looking for $c_n:=a_n+b_n$.
Note that $c_1=1+2=3, c_2=2+6=8, c_3=6+16=22, \ldots$
We can write 
$$\left(\begin{matrix}a_{n+1}\\b_{n+1}\end{matrix}\right)=\left(\begin{matrix}0&1\\2&2\end{matrix}\right)\left(\begin{matrix}a_{n}\\b_{n}\end{matrix}\right)$$
and therefore look for eigenvalues of this matrix, that is roots of $x^2-2x-2=0$, i.e. $x=+1\pm\sqrt 3$. Then $c_n$ will be expressible as 
$$c_n=\alpha(1+\sqrt 3)^n+\beta(1-\sqrt 3)^n$$
for suitable $\alpha, \beta$.
From $c_0=1, c_1=3$, we infer $\alpha=\frac12+\frac1{\sqrt3}$ and $\beta=\frac12-\frac1{\sqrt3}$.
