I was given the following problem:
Find the closed formula that determines the number of r-digits quaternary sequences (made of 0's, 1's, 2's and 3's) in which: (i) the number of 0's is even and (ii) the first 3 appears before any occurrences of 1's and 2's.
I managed to come up with the following recurrence relation $(r\ge2)$ :
$$ a_r = b_{r-1} + c_{r-1} $$ $$ b_r = a_{r-1} - c_{r-1} + 4^{r-1} $$ $$ c_r = 2c_{r-1} + 4^{r-1} $$ $$ a_1 = 1 \quad b_1 = 0 \quad c_1 = 3 $$
$a_n$ are the sequences with the constraints given in the problem. $b_n$ is the almost the same, except that the number of zeroes is odd. $c_n$ are the quaternary sequences with an even number of zeroes (no constraints for 3).
The real problem for me lies in discovering the formula. I tried to use generating functions, which gave me:
$$ c_r = \frac12(-(2^r)+4^r)$$
But apparently that's incorrect, as it gives wrong values for $c_r$. However, even if that was correct, finding $a_n$ would require some really tough algebra, which probably indicated that it was not the correct way of doing things.
I would like some hints on how to go forward with this recurrence relation, using or not using generating functions (preferably not using).
I approached it a little differently. This may not be the most efficient approach, but it worked straightforwardly.
Say that a quaternary sequence is good if the first $3$ appears before any $1$ or $2$. Let $a_n$ be the number of good $n$-place sequences that have an even number of $0$s, and let $b_n$ be the number of good $n$-place sequences that have an odd number of $0$s. These numbers satisfy the following recurrences:
$$\begin{align*} a_n&=3a_{n-1}+b_{n-1}-2[n\text{ is odd}]\\ b_n&=3b_{n-1}+a_{n-1}-2[n\text{ is even}]\;, \end{align*}\tag{1}$$
where the square brackets are Iverson brackets.
To see this, suppose that $\sigma$ is a good sequence of length $n$ with an even number of $0$s. If $\sigma=\tau0$, then $\tau$ is a good sequence of length $n-1$ with an odd number of $0$s. Conversely, if $\tau$ is such a sequence, then $\tau0$ is a good sequence of length $n$ with an even number of $0$s. This accounts for the $b_{n-1}$ term in the first recurrence. If $\sigma=\tau k$ for $k\in\{1,2,3\}$, then $\tau$ is a good sequence of length $n-1$ with an even number of $0$s. Conversely, if $\tau$ is such a sequence, and $k\in\{1,2,3\}$, then $\tau k$ is a good sequence of length $n$ with an even number of $0$s unless $\tau$ is the zero sequence of length $n-1$ and $k\in\{1,2\}$, in which case the sequences $\tau1$ and $\tau2$ are not good. However, this happens only when $n$ is odd, since the zero sequence $\tau$ is of length $n-1$ and has an even number of $0$s. These observations account for the terms $3a_{n-1}-2[n\text{ is odd}]$ and establish the first recurrence. The second recurrence is proved similarly.
Now let $c_n=a_n+b_n$; $(1)$ implies that $c_n=4c_{n-1}-2$. Moreover, $a_0=1$ and $b_0=0$, so $c_0=1$. If we set $c_{-1}=0$, the recurrence
$$c_n=4c_{n-1}-2+3[n=0]$$
holds for all $n\ge 0$. Multiplying by $x^n$ and summing over $n\ge 0$, we have
$$\begin{align*} \sum_{n\ge 0}c_nx^n&=4\sum_{n\ge 0}c_{n-1}x^n-2\sum_{n\ge 0}x^n+3\\ &=4x\sum_{n\ge 0}c_nx^n-\frac2{1-x}+3\\ &=4x\sum_{n\ge 0}c_nx^n+\frac{1-3x}{1-x}\;. \end{align*}$$
Let $C(x)=\sum_{n\ge 0}c_nx^n$ be the ordinary generating function for $\langle c_n:n\in\Bbb N\rangle$, solve for $C(x)$, decompose into partial fractions, and convert to a power series:
$$C(x)=\frac{1-3x}{(1-x)(1-4x)}=\frac13\left(\frac2{1-x}+\frac1{1-4x}\right)=\frac13\sum_{n\ge 0}\left(4^n+2\right)x^n\;.$$
Thus, $c_n=\dfrac{4^n+2}3$, and
$$\begin{align*} a_n&=3a_{n-1}+b_{n-1}-2[n\text{ is off}]\\ &=2a_{n-1}+c_{n-1}-2[n\text{ is odd}]\\ &=2a_{n-1}+\frac{4^{n-1}+2}3-2[n\text{ is odd}]+\frac14[n=0]\;, \end{align*}$$
where the last term is to make $a_0=1$ on the assumption that $a_{-1}=0$.
Now let $A(x)=\sum_{n\ge 0}a_nx^n$, and repeat the process that I used above to determine $C(x)$:
$$\begin{align*} A(x)&=2xA(x)+\frac13\sum_{n\ge 0}\left(4^{n-1}+2\right)x^n-2x\sum_{n\ge 0}x^{2n}+\frac14\\ &=2xA(x)+\frac1{12}\left(\frac8{1-x}+\frac1{1-4x}\right)-\frac{2x}{1-x^2}+\frac14\\ &=2xA(x)+\frac{2/3}{1-x}+\frac{1/12}{1-4x}-\left(\frac1{1-x}-\frac1{1+x}\right)+\frac14\\ &=2xA(x)-\frac{1/3}{1-x}+\frac{1/12}{1-4x}+\frac1{1+x}+\frac14\;, \end{align*}$$
so
$$\begin{align*} A(x)&=-\frac{1/3}{(1-x)(1-2x)}+\frac{1/12}{(1-4x)(1-2x)}+\frac1{(1+x)(1-2x)}+\frac{1/4}{1-2x}\\ &=\frac13\left(\frac1{1-x}-\frac2{1-2x}\right)+\frac1{12}\left(\frac2{1-4x}-\frac1{1-2x}\right)+\frac13\left(\frac1{1+x}+\frac2{1-2x}\right)+\frac{1/4}{1-2x}\\ &=\frac1{12}\left(\frac4{1-x}+\frac2{1-2x}+\frac4{1+x}+\frac2{1-4x}\right)\\ &=\frac16\sum_{n\ge 0}\big(2+2^n+2(-1)^n+4^n\big)x^n\;, \end{align*}$$
and
$$a_n=\frac{1+(-1)^n+2^{n-1}+2^{2n-1}}3=\frac{1+(-1)^n+2^{n-1}(2^n+1)}3\;.$$
(The $1+(-1)^n$ in the numerator is ultimately the result of the $[n\text{ is odd}]$ term in the recurrence.)