Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.

Question

Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.

Analyzing the question means that the pair (2,2) where-ever it appear is making the problem.

Then i'm asking myself, How can i, Using 'recursional thinking', solve this kind of question?

Answer 1

Try thinking of it this way:

Suppose that you have an $n-1$ length series. Now, you want to add a new number onto the end of it. If the last digit of your $n-1$ length series is a $2$, then you can only add $0$ or $1$. If it's a $0$ or $1$, then you can add anything.

Let $T_k$ be the number of series of length $k$ ending in $2$, and let $Z_k$ be the number of series of length $k$ ending in $0$ or $1$. Let $N_k=T_k+Z_k$ be the total number of series of length $k$. Then we have

$$ T_{k+1} = Z_k $$ because you can only add a $2$ to the end of a series ending in $0$ or $1$.

$$ Z_{k+1} = 2N_k $$ because you can add either a zero or a 1 onto any series. Now, we have $$ N_{k+1} = T_{k+1} + Z_{k+1} = Z_k + 2N_k = 2N_{k-1}+2N_k $$ So you have your recursion, in the form $$ N_{k+1} = 2(N_k+N_{k-1}) $$ So you just need starting values. Obviously $N_1=3$. Now you can define $N_0=1$ if you don't mind the seemingly-arbitrary choice, or you can note that for length $2$, you have $00,01,02,10,11,12,20,21$, for a total of $8$, and so $N_2=8$.

Note that this satisfies, as $8 = 2(3+1)$.

Answer 2

Let $a_n$ be the number of sequences of length $n$ with elements from $\{0,1,2\}$ such that the sum of adjacent terms is always at most $3$. As you observed, this just means that the subsequence $22$ is not allowed. Call such $n$-sequences good for short.

Consider a good $n$-sequence $d_1d_2\dots d_{n-1}d_n$. Clearly $d_1\dots d_{n-1}$ is a good $(n-1)$-sequence. No matter which of the $a_{n-1}$ good $(n-1)$-sequences it is, $d_1\dots d_{n-1}0$ and $d_1\dots d_{n-1}1$ are good $n$-sequences. Looking at that in reverse, if $d_n$ is $0$ or $1$, we can construct the $n$-sequence $d_1d_2\dots d_{n-1}d_n$ by appending $0$ or $1$ to one of the good $(n-1)$-sequences. Thus, there are $a_{n-1}$ good $n$-sequences that end in $0$, and also $a_{n-1}$ that end in $1$.

The good $n$-sequences that end in $2$ are a little trickier: a good $(n-1)$-sequence that ends in $2$ cannot be extended to a good $n$-sequence that ends in $2$. To get a good $n$-sequence ending in $2$, go back one more step and look at the $(n-2)$-sequence $d_1\dots d_{n-2}$. It’s good, so there are $a_{n-2}$ possibilities for it, and no matter what it is, we can extend it with $02$ or $12$ to get a good $n$-sequence ending in $2$. Thus, there are $2a_{n-2}$ good $n$-sequences ending in $2$.

Now just put the pieces together, and you have your recurrence for $a_n$.

Added: An alternative approach is to start with three sequences: let $b_n$ be the number of good $n$-sequences that end in $0$, $c_n$ the number that end in $1$, and $d_n$ the number that end in $2$. Of course $a_n=b_n+c_n+d_n$. Now it’s easy to see that

$$\begin{align*} b_n&=b_{n-1}+c_{n-1}+d_{n-1}=a_{n-1}\\ c_n&=b_{n-1}+c_{n-1}+d_{n-1}=a_{n-1}\\ d_n&=b_{n-1}+c_{n-1}\;: \end{align*}\tag{1}$$

you can get a good $n$-sequence ending in $0$ by appending a $0$ to any good $(n-1)$-sequence, no matter what it ends in, and similarly for good $n$-sequences ending in $1$, but to get a good $n$-sequence ending in $2$, you must append the $2$ to a good $(n-1)$-sequence ending in $0$ or $1$.

Adding the equations in $(1)$, we get

$$a_n=2a_{n-1}+b_{n-1}+c_{n-1}=2a_{n-1}+a_{n-2}+a_{n-2}=2a_{n-1}+2a_{n-2}\;.$$

Answer 3

If I understand correctly, you want to know how many sequences of length $n$ (call them $a_n$) are formed by pairs $[x, y]$ where $x, y \in \{0, 1, 2\}$ and $1 \le x + y \le 3$. This is just: $$ a_n = u_1 a_{n - 1} + u_2 a_{n - 2} + u_3 a_{n - 3} $$ where $u_i$ is the number of pairs giving $i$: $$ \begin{align*} u_1 &= 2 &&[0, 1], [1, 0] \\ u_2 &= 3 &&[0, 2], [1, 1], [2, 0] \\ u_3 &= 2 &&[1, 2], [2, 1] \end{align*} $$ Incidentally, $a_n = u_n$ for $1 \le n \le 3$

Rewrite the recurrence as: $$ a_{n + 3} = 2 a_{n + 2} + 3 a_{n + 1} + 2 a_n \qquad a_0 = 1, a_1 = 2, a_2 = 3 $$ Define the generating function $A(z) = \sum_{n \ge 0} a_{n + 1} z^n$, so: $$ \frac{A(z) - a_1 - a_2 z - a_3 z^2}{z^3} = 2 \frac{A(z) - a_1 - a_2 z}{z^2} + 3 \frac{A(z) - a_1}{z} + 2 A(z) $$ So that: $$ A(z) = \frac{2 - z - 10 z^2}{1 - 2 z - 3 z^2 - 2 z^3} $$ Next step is to split this into partial fractions, but the roots of the denominator turn out really ugly.

The help of maxima with the algebra is gratefully acknowledged.