Number of sequences $(a_1, . . . , a_n)$, with elements from the set $\{ 0, 1, 2 \}$, satisfying: $|a_k - a_{k-1}| \leq 1$ for $k = 2, 3, . . ., n$.

Question

Determine the number of sequences $(a_1, a_2, . . . , a_n)$, with elements from the set $\{ 0, 1, 2 \}$, satisfying the condition $|a_k - a_{k-1}| \leq 1$ for $k = 2, 3, . . ., n$.

We know that if I define the number of sequences for a given $n$ as $a_n$, then: $$a_n = 3a_{n-1} + 2a_{n-1} + 2a_{n-1} = a_n = 7a_{n-1}$$

The equality holds because if we know that:

• the last element was equal to $1$, then semi-last element could be equal to: $0$, $1$ or $2$, so we have $3$ options
• the last element was equal to $0$, then semi-last element could be equal to: $0$ or $1$, so we have $2$ options
• the last element was equal to $2$, then semi-last element could be equal to: $1$ or $2$, so we have $2$ options

From that we have: $$a_n = k \cdot 7^n$$

We know that $a_1 = 3$, because that one element can be equal to: $0$, $1$ or $2$, so we have $3$ options. Therefore:

$$a_n = \frac{3}{7} \cdot 7^n = 3 \cdot 7^{n-1}$$

Is that correct?

Answer 1

Another solution which is simpler.

Denote $(A_n,B_n,C_n)$ the number of sequences for a given $n$ that begins with $0$, $1$ or $2$. We observe that: $$\begin{align} &A_{n+1} = A_n + B_n\\ &B_{n+1} = A_n + B_n+C_n\tag{1}\\ &C_{n+1} = B_n +C_n\\ \end{align}$$

Denote $P(n)$ the total number of sequences of length $n$, then $P(n) = A_n + B_n +C_n$. From $(1)$, we have:

$$P(n+1) = A_{n+1}+B_{n+1} +C_{n+1} = 2\underbrace{(A_n + B_n+C_n)}_{= P(n)} + \underbrace{B_n}_{= A_{n-1}+B_{n-1} +C_{n-1} = P(n-1)}$$ $$\implies \color{red}{P(n+1) = 2P(n) +P(n-1)} \tag{2}$$ It's easy to solve the quadratic sequence $(2)$: if $x_{1,2}= (1\pm \sqrt{2})/2$ the two solutions of the quadratic equation $x^2 - 2x -1 =0$ then $$P(n) = p_1\cdot x_1^{n}+p_2\cdot x_2 ^n \tag{3}$$

Determine $(p_1,p_2)$ from $(3)$ given that $P(1) = 3$ and $P(2) = 7$, we can show that $$\color{red}{P(n) = \frac{(\sqrt{2}+1)^{n+1}+(1-\sqrt{2})^{n+1}}{2}}$$

Answer 2

Denote $(A_n,B_n,C_n)$ the number of sequences for a given $n$ that begins with $0$, $1$ or $2$. We observe that: $$\begin{align} &A_{n+1} = A_n + B_n\\ &B_{n+1} = A_n + B_n+C_n\tag{1}\\ &C_{n+1} = B_n +C_n\\ \end{align}$$ Write $(1)$ in matrix form: $$\underbrace{\pmatrix{A_{n+1}\\B_{n+1}\\C_{n+1}}}_{:=X_{n+1}}= \underbrace{\pmatrix{1&1&0\\1&1&1\\0&1&1}}_{:=M}\cdot\underbrace{\pmatrix{A_{n}\\B_{n}\\C_{n}}}_{:=X_{n}}$$ Diagonalize $M=U^{-1}DU$ where $$\begin{align} &U=\pmatrix{1&\sqrt{2}&1\\-1&0&1\\1&-\sqrt{2}&1}\\ &D=\pmatrix{1 + \sqrt{2}&0&0\\0&1&0\\0&0&1 - \sqrt{2}}\end{align}$$ Then $$(2)\iff X_{n+1} = U^{-1}D UX_n\iff (UX_{n+1})=D\cdot (UX_n)=...=D^n\cdot (UX_1)$$ $$\implies X_n = U^{-1}D^{n-1}U X_1 = U^{-1}\cdot \pmatrix{(1 + \sqrt{2})^{n-1} &0&0\\0&1&0\\0&0&(-1)^{n-1}(\sqrt{2} - 1)^{n-1}}\cdot U\cdot X_1 $$ If we denote $t = 1+\sqrt 2$ and $v = (-1)^{n-1}$ then thanks to WolframAlpha, the matrix $\Lambda_n:= U^{-1}D^{n-1}U \in \mathbb{R}^{3\times 3}$ can be computed easily.

$$X_n = \Lambda_n X_1 \tag{2}$$

As $X_1 =(1,1,1)'$, $A_n,B_n,C_n$ are equal to the sum of the row of $\Lambda_n$. And if we denote the number of sequences for a given $n$ by $P(n)$, we have $P(n) = A_n + B_n + C_n$, then $P(n)$ is equal to the sum of all elements of $\Lambda_n$ (the matrix $\Lambda_n$ can be found in the link WolframAlpha): $$\color{red}{P(n) = \frac{(\sqrt{2}+1)^{n+1}+(1-\sqrt{2})^{n+1}}{2}}$$ Remark: We can compute the sum via WolframAlpha by $\mathbb{1}'\cdot \Lambda_n\cdot \mathbb{1}$ (where $\mathbb{1} = (1,1,1)'$) as in this link.