Recurrence for the number of n tuples with restrictions

Question

If $a_{n}$ is the number of $n$ tuples $(b_{1}, b_{2},...b_{n})$ with $b_{i} \in[4]$ that have at least one 1 and have no 2 appearing before the first 1. What is the recurrence for $a_{n}$?

Answer 1

Instead of approaching via recurrence relations, let us instead look at it in the following manner.

Count the number of such sequences which has the first one appearing at the $i^{th}$ spot and no two before the first one by:

• Count how many prefixes exist: $2^{i-1}$
• Count how many suffixes exist: $4^{n-i}$

Applying multiplication principle, there are $2^{i-1}\cdot 4^{n-i} = 2^{i-1+2n-2i} = 2^{2n-1}\cdot 2^{-i}$ such sequences with $1$ as the $i^{th}$ spot with no twos before it.

Ranging over all possible locations for the first one, we have the following summation:

$$a_n = \sum\limits_{i=1}^n 2^{2n-1}2^{-i} = 2^{2n-1}\left(\sum\limits_{i=1}^n (\frac{1}{2})^i\right) = 2^{2n-1}(1-2^{-n}) = 2^{2n-1}-2^{n-1}$$

---

If you insist on approaching via recurrence relations, you should not only keep track of $a_n$ but also of the number of sequences with no $1$'s and no $2$'s.

Given an arbitrary "good" sequence, one of two things will be true: the final entry is the first one, the final entry is not the first one.

If the final entry is the first one, then what comes before it must be a sequence with no 1's and no 2's. This will contribute $2^{n-1}$ to the total sum.

If the final entry is not the first one, then what precedes it is a valid "good" sequence and the final entry is allowed to be anything from our list (1,2,3,4). This contributes $4a_{n-1}$ to our total.

This gives the recurrence relation:

$$a_n = 4a_{n-1}+2^{n-1}$$

Solving should bring you to the answer I gave above as the final answer (albeit possibly written differently but equal).

Indeed, solving this, we get the characteristic polynomial $x-4=0$, so we expect the answer should look like $a_n = c_1 4^n + c_2 2^n$ for some constants $c_1,c_2$ to be determined. It is clear also that we have initial conditions $a_0=0$ and $a_1=1$.