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.

We call a number to be good if none of two consecutive digits differ by more than one. How many good $n$-digits numbers made from digits $1$, $2$ and $3$ are there?

For example, $12232$ is good, but $12\textbf{31}2$ isn't.

My idea was to subtract bad numbers made of $1$, $2$ and $3$ (bad numbers are ones that aren't good) from $3^n$ (which represents number of $n$-digit numbers made of $1$, $2$ and $3$).

I tried with representing number $abcd$ ($n=4$) as sequence of 3 ($4-1$) pairs of digits: $(a,b),\text{ }(b,c),\text{ }(c,d)$. Then (I think) we could count number of ways to have at least one of the pairs $(1,3)$ and $(3,1) appearing at least once. But alas...

share|improve this question
add comment

2 Answers 2

Let $A_n, B_n, C_n$ be the number of ways an $n-$digit number satisfies the condition, and starts with $1, 2, 3$ respectively. We have $A_1 = B_1 = C_1 = 1$. We are looking for $A_n + B_n + C_n$.

The recurrence relation is $A_{n+1} = A_n + B_n$, $B_{n+1} = A_n + B_n + C_n$, $C_{n+1} = B_n + C_n$. By symmetry, we have $C_n = A_n$.

Claim: $A_n \sqrt{2} +B_n= (\sqrt{2}+1 )^{n+1}$.

Proof: This is true for $n=1$. Proceed by induction to show that the recurrence relation is satisfied. $_\square$

Similarly, $A_n \sqrt{2} - B_n = (\sqrt{2} -1)^{n+1}$. This allows you to obtain closed forms for $A_n$ and $B_n$.

share|improve this answer
add comment

Let the $n$ digit number be $a_1 a_2 \ldots a_n$. Let $N_1(n)$ be the number of $n$ digit numbers that are good starting with $1$, $N_2(n)$ be the number of $n$ digit numbers that are good starting with $2$ and , $N_3(n)$ be the number of $n$ digit numbers that are good starting with $3$. We have \begin{align} N_1(n) & = N_1(n-1) + N_2(n-1)\\ N_2(n) & = N_1(n-1) + N_2(n-1) + N_3(n-1)\\ N_3(n) & = N_2(n-1) + N_3(n-1) \end{align} Hence, we have $$\begin{bmatrix}N_1(n)\\ N_2(n)\\ N_3(n) \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 &1\end{bmatrix}}_A \begin{bmatrix} N_1(n-1)\\ N_2(n-1)\\ N_3(n-1) \end{bmatrix}$$ Hence, $$\vec{N}(n+1) = A^n \vec{N}(1)$$ We have $$V = \dfrac12 \begin{bmatrix} 1 & -\sqrt2 & 1\\ -\sqrt2 & 0 & \sqrt 2\\ 1 & \sqrt2 & 1\end{bmatrix}$$ and $$\Lambda = \begin{bmatrix} 1-\sqrt2 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 +\sqrt2\end{bmatrix}$$ and $$A = V \Lambda V^T$$ Hence, $$\vec{N}(n+1) = V \Lambda^n V^T \vec{N}(1)$$ where $$\vec{N}(1) = \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}$$ Hence, the answer is \begin{align} N_1(n) + N_2(n) + N_3(n) & = \begin{bmatrix} 1 & 1 & 1\end{bmatrix} V \Lambda^n V^T \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}\\ & = \dfrac14\begin{bmatrix} 2-\sqrt{2} & 0 & 2+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} 2-\sqrt{2} \\ 0 \\ 2+\sqrt{2}\end{bmatrix}\\ & = \dfrac12\begin{bmatrix} \sqrt{2}-1 & 0 & 1+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} \sqrt{2}-1 \\ 0 \\ 1+\sqrt{2}\end{bmatrix}\\ & = \dfrac{(1+\sqrt2)^{n+1} + (1-\sqrt2)^{n+1}}2 \end{align}

share|improve this answer
add comment

Your Answer

 
discard

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.