Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].

Question

Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].

So what i did was:

1. Let $a_n$ be the total number of series length n so that each pair has the correct sum.
2. Let $b_n$ be total number of series starting with $0$.
3. Let $c_n$ be total number of series starting with $1$.
4. Let $d_n$ be total number of series starting with $2$.

Notice that $a_n=b_n+c_n+d_n$.

Recursion relation of $b_n=c_{n-1}+d_{n-1}$ -This makes sure there are no $0,0$.

Recursion relation of $c_n=a_{n-1}$ - Doesn't matter which digit is next.

Recursion relation of $d_n=b_{n-1}+c_{n-1}$ -This makes sure there are no $2,2$.

First off, Did i look at the question right? If so, I'm pretty much stuck on simplifying those recursion relation.

Answer 1

Yes, this is a reasonable way to start, though you really want $b_n,c_n$, and $d_n$ to count the number of strings ending in $0,1$, or $2$, respectively, not starting with those digits. Your three recurrences are correct:

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

Notice that if you subtract the third from the first, you get $$b_n-d_n=d_{n-1}-b_{n-1}=-(b_{n-1}-d_{n-1})\;.\tag{2}$$ You can easily check that $b_1=d_1=1$, so $b_1-d_1=0$, and an easy proof by induction using $(2)$ shows that $b_n=d_n=0$ for all $n\ge 1$, i.e., that $b_n=d_n$. (This is intuitively very reasonable: if you start with a good sequence and change all of the $0$’s to $2$’s and vice versa, you get a good sequence. Thus, the number ending in $0$ and the number ending in $2$ should be the same.)

Now we can simplify $(1)$:

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

Moreover,

$$\begin{align*} a_n&=2b_n+c_n\\ &=2b_n+a_{n-1}\\ &=2(a_{n-2}+b_{n-1})+a_{n-1}\\ &=2a_{n-2}+2b_{n-1}+a_{n-1}\\ &=a_{n-2}+(a_{n-2}+2b_{n-1})+a_{n-1}\\ &=a_{n-2}+(c_{n-1}+2b_{n-1})+a_{n-1}\\ &=a_{n-2}+a_{n-1}+a_{n-1}\\ &=a_{n-2}+2a_{n-1}\;. \end{align*}$$

Let’s check by using the other approach. If I start with a good $(n-1)$-sequence, there are always two digits that I can safely add. (Why?) That accounts for $2a_{n-1}$ good $n$-sequences. If the $(n-1)$-sequence ends in $1$, I can add any of the three digits, so I need to know how many of the good $(n-1)$-sequences end in $1$. Each of those can be obtained by adding a $1$ to a good $(n-2)$-sequence, so there are $a_{n-2}$ of them, and we again get the recurrence $a_n=2a_{n-1}+a_{n-2}$.

In this problem I really think that the second approach is easier unless you’re familiar with matrix methods or generating functions.

Answer 2

You have set up the recurrence nicely. I would ignore $a_n$ for now and rewrite $c_n=b_{n-1}+c_{n-1}+d_{n-1}$ to avoid the relation between the $_n$ terms. You could also use the symmetry that tells you $b_n=d_n$ to get to two recurrences instead of three. You also need some initial conditions. Now note that if you have a column vector $\begin {bmatrix} b_n\\c_n\\d_n \end {bmatrix}$ it satisfies the recursion $$\begin {bmatrix} b_n\\c_n\\d_n \end {bmatrix}=\begin {bmatrix} 0&1&1\\1&1&1\\1&1&0 \end {bmatrix}\begin {bmatrix} b_{n-1}\\c_{n-1}\\d_{n-1} \end {bmatrix}$$ As the matrix is symmeteric, it will have a complete set of eigenvalues. Find them and the corresponding eigenvectors, then the linear combination that represents your initial conditions.

Answer 3

Define generating functions $A(z) = \sum_{n \ge 0} a_{n + 2} z^n$ and so on (need at least length 2). Write your system as: $$ \begin{align*} b_{n + 1} &= c_n + d_n \\ c_{n + 1} &= b_n + c_n + d_n \\ d_{n + 1} &= b_n + c_n \end{align*} $$ Then $b_2 = c_2 = d_2 =2$, and: $$ \begin{align*} \frac{B(z) - b_2}{z} &= C(z) + D(z) \\ \frac{C(z) - c_2}{z} &= B(z) + C(z) + D(z) \\ \frac{D(z) - d_2}{z} &= B(z) + C(z) \end{align*} $$ And also: $$ A(z) = B(z) + C(z) + D(z) $$ Solve the linear system for $B(z)$, $C(z)$, $D(z)$, plug into $A(z)$. Split $A(s)$ into partial fractions (possibly with complex roots!), and expand each term by the binomial theorem: $$ (1 - u)^{-m} = \sum_{n \ge 0} \binom{k + m - 1}{m - 1} u^n $$ Profit!