3
$\begingroup$

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.

  • 0
    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.2012-12-12

2 Answers 2

4

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

2

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