Let $q_n$ be the number of words of length n in the alphabed $\{a, b, c, d\}$ that contains an odd number of b's.
- Prove that for all $n \geq 0$, then $q_{n+1} = 4^n + 2 *q_n \tag{1}\label{eq1}$
- Deduce that $q_n = \frac{4^n - 2^n}{2}$
My approach in solving this question is in \eqref{eq1},i divide and conquer in that i consider some-words that begin with a b or not. Somehow the approach makes sense but i cant seem to gain the traction to solve it.
In the second part however, i decided to go for induction.
I've solved quite a number of induction examples but i dont know why this task seems a bit unique to think through. I even thought of using probability but it seems like a long shot in hindsight
I)
There are $4^n$ $n$ letter words. If $q_n$ of them have an odd number of $b$s then $4^n - q_n$ have an even number of $b$s.
For each $n$ letter word with an odd number of $b$s, we can create $3$ possible $n+1$ letter words with an odd number of $b$s by adding $a,c$ or $d$ to the end. There are $3*q_n$ such words we can make this way.
For each $n$ letter word with an even number of $b$s, we can create a $n+1$ letter word with an odd number of $b$ by adding $b$ to the end. This is $4^n - q_n$ such words we can make this way.
That accounts for all $n+1$ letter words with an odd number of $b$s. (Each $n+1$ letter word is a $n$ letter word with a letter added to the end. So this is sufficient to account for all possible $n+1$ letter words with an odd number of $b$s.)
And there are $q_{n+1} = 3*q_n + 4^n - q_n = 4^n + 2*q_n$ such words.
II)
Base step: $q_1 = 1$. There is exactly one, $1$ letter word with an odd number of $b$s. It is "$b$".
Induction step: suppose $q_n = \frac {4^n - 2^n}2$ and we know from I) that $q_{n+1} = 4^n + 2*q_n = 4^n + 2(\frac {4^n-2^n}2)$ then
$q_{n+1} =4^n + 2*q_n = $ $4^n + 2(\frac {4^2-2^n}2) = $
$4^n + 4^n - 2^n = $
$2*4^n - 2^n = $
$\frac {4*4^n - 2*2^n}2 = $
$\frac {4^{n+1} - 2^{n+1}}2$
That's it.