# 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.

-
You're mistaken anyway: for $n=3$ it's $22$: 121 122 123 131 132 133 212 213 221 222 223 231 232 233 312 313 321 322 323 331 332 333. – Clive Newstead Dec 12 '12 at 15:52

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
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}$.