Number of sequences of length $n \geq 1$ with elements from set $ \{0,1,2,3,4 \} $ such that blocks of $0$s, $2$s and $4$s are of even length.

Question

Question statement:

In a sequence $\langle a_1, ...,a_n \rangle$ a block is every maximal subsequence of same digits. For example, in a sequence $\langle 0, 0, 3, 1, 2, 2, 2, 2, 4, 4 \rangle$ there are $5$ blocks:

• blocks of $0$s and $4$s, of length $2$,
• block of $2$s of length $4$,
• blocks of $1$s and $3$s, of length $1$.

How many sequences of length $n \geq 1$ with elements from set $ \{0,1,2,3,4 \} $ such that every block of $0$s, $2$s and $4$s is of even length (but a given digit can not appear in the sequence at all) exist? Find the closed-form expression with argument $n$.

---

My proposed solution:

First two elements of sequence:

1. $a_1 = 2$, because we choose one of $2$ digits
2. $a_2 = 7$, because we choose digits from the set: $\{1,3 \}$ and put them in any combination on those $2$ places ($11, 13, 31, 33$) or alternativelly, we choose one of $3$ blocks made of digits from the set: $\{0,2,4 \}$. Those are: $00$s, $22$s and $44$s
3. $a_3 = 2*2*2 + 3*2*2 = 20$ (odd digits only: we choose one of $2$ digits for each one of $3$ places, even digits only: there is no way, since we have $3$ places in our equation, odd digits with even digits: we choose the block of even digits out of $3$ possible, then we place it on first or second place, then for the remaining place we choose one of $2$ odd digits)
4. $a_4 = 2*2*2*2 + 3*3 + 3*2*2 + 2*2*3 + 2*3*2 = 25 + 36 = 61$ (odd digits only: we choose one of $2$ digits for each one of $4$ places, even digits only: we choose $2$ blocks of even digits out of $3$ possible, odd digits with even digits: we choose the block of even digits out of $3$ possible, then we place it on first, second or third place, then for the remaining $2$ placs we choose one of $2$ odd digits).

Generalization for all other elements of sequance:

• if on the last place, $n$, there is $0$, $2$ or $4$, then there had to be $0$, $2$ or $4$ before that (on place $n-1$) and a 'correct sequence' on former places (from $1$ to $n-2$). So we choose one of $3$ pairs of digits ($00, 22, 44$) for places: $n$ and $n-1$ and then copy our choices for former places ($n-2$).
• if on the last place there is $1$ or $3$ there had to be a 'correct sequence' on former places: $[1, n-1]$. So we choose one of $2$ digits ($1, 3$) for $n$ place and copy our choices for former places ($n-1$).

So I came with a recursive formula: $a_n = 2a_{n-1} + 3a_{n-2}$. From that I get: $\lambda^2 - 2\lambda - 3 = 0$.

I need to solve that equation, so thats what I do:

$\Delta = 4 - 4 \cdot (-3) = 16$

$\sqrt{\Delta} = 4$

• $\lambda_1 = \frac{2 - 4}{2} = -1$
• $\lambda_2 = \frac{2 + 4}{2} = 3$

From that I know that the closed form solution is equal to: $a_n = a(-1)^n + b(3)^n$ for some parameters $a$ and $b$. To find those, I plug in values of $a_1$ and $a_2$ that I've already found.

• $a_1 = 2 = -a + 3b \iff 2 + a = 3b \iff b = \frac{2 + a}{3}$
• $a_2 = 7 = a + 9b \iff 7 = a + 9 \left( \frac{2+a}{3} \right) \iff 7 = a + 6 + 3a \iff 4a = 1 \iff a = \frac{1}{4}$

$b = \frac{2 + \frac{1}{4}}{3} = \frac{8 + 1}{12} = \frac{3}{4}$

So, finaly, the closed form solution is equal to:

$a_n = \frac{1}{4}(-1)^n + \frac{3}{4}(3)^n$

I test it for my former foud elements $a_3$ and $a_4$:

• $a_3 = \frac{1}{4}(-1)^3 + \frac{3}{4}(3)^3 = -\frac{1}{4} + \frac{3}{4} \cdot 27 = \frac{80}{4} = 20$
• $a_4 = \frac{1}{4}(-1)^4 + \frac{3}{4}(3)^4 = \frac{1}{4} + \frac{3}{4} \cdot 81 = \frac{1}{4} + \frac{243}{4} = \frac{244}{4} = 61$

It looks to be working.

---

Now we can prove that its right using induction.

We have the basis for $a_3$ and $a_4$ already done. Then we assume that formula $a_n = \frac{1}{4}(-1)^n + \frac{3}{4}(3)^n$ works for $n-1$ and for $n$. We need to make the induction step:

• $a_{n-1} = \frac{1}{4}(-1)^{n-1} + \frac{3}{4}(3)^{n-1}$
• $a_{n} = \frac{1}{4}(-1)^{n} + \frac{3}{4}(3)^{n}$

We have:

$$a_{n+1} = 2a_{n} + 3a_{n-1} = 2 \left( \frac{1}{4}(-1)^{n} + \frac{3}{4}(3)^{n} \right) + 3 \left( \frac{1}{4}(-1)^{n-1} + \frac{3}{4}(3)^{n-1} \right) =$$ $$= \frac{2}{4}(-1)^{n} + \frac{6}{4}(3)^{n} + \frac{3}{4}(-1)^{n-1} + \frac{9}{4}(3)^{n-1} =$$ $$= -\frac{2}{4}(-1)^{n-1} + \frac{18}{4}(3)^{n-1} + \frac{3}{4}(-1)^{n-1} + \frac{9}{4}(3)^{n-1} =$$ $$= \frac{1}{4} \cdot 1 (-1)^{n+1} + \frac{3}{4}\cdot 9 (3)^{n-1} =$$ $$= \frac{1}{4}(-1)^{n+1} + \frac{3}{4} (3)^{n+1}$$

And as we see, the formula works fine.

Answer 1

The formula you listed appears to be a correct solution. You have a simple arithmetic error, that made you draw the wrong conclusion.

$$-\frac14 + \frac34 \cdot 27 = -\frac14 + \frac{81}{4} = \frac{80}{4} = 20.$$

Perhaps you missed the negative sign; $-1+81=80$, not $82$.