Let $q_n$ be amount of sequences, where length of sequence is $n$. The sequences are constructed from elements $\in \{a,b,c,d\}$ . In sequecne 'b' occurs odd times. For example: $$n = 10$$ $$aabbcacacb$$ number of 'b' is three so this sequence is correct.
Prove that $$q_n = 4^{n-1} + 2q_{n-1}$$ I am going to consider the secuences of ${n-1}$ length and try to it make longer. I am asking for advice.
Also define $r_n$ as the number of sequences of length $n$ where $b$ appears an even number of times. Clealry $r_n+q_n=4^n$ We have $q_n=3q_{n-1}+r_{n-1},$ because you can extend a sequence three ways without changing the parity and one way changing the parity. Then $q_n=3q_{n-1}+4^{n-1}-q_{n-1}=4^{n-1}+2q_{n-1}$
Take any sequence of length $n-1$ (There are $4^{n-1}$ of these ) , if it has an odd number of $b$'s add an $a$ at the end, if it has an even number of $b's$ add a $b$ at the end. We now have counted all the desired sequences that end in $a$ or $b$.
We need to count those that end in $c$ or $d$. There are $q_{n-1}$ of each. Why? if you take a desired sequence ending in $c$ and remove the last element you get a sequence of length $n-1$ that satisfies the initial conditions.
