Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.