I have a recurrence relation problem that states the following:
Given the alphabet $\sum = \{a,b,c\}$ how many words can be formed that have an uneven amount of "a"'s
From my understanding: Each time the length of the word is increased by one, the are $3^n$ more possible words:
$x_0 = \lambda$
$x_1 = a \lor b \lor c$
$x_2 = aa \lor ab \lor ac \lor ba \lor bb \lor bc \lor ca \lor cb \lor cc$
And so on.
Besides, from the examples I gave I can see the following "pattern"
$x_0 = 0 $ (0 referring to the amount of words with uneven a's)
$x_1 = 1$ (a)
$x_2 = 4$ (ab,ac,ba,ca)
But even "knowing" all of this, I'm not able to deduce the answer. According to my professor the recurrence relation is: $x_{n+1} = 2x_n + (3^n - x_n)$; and the solution is $x_n = \frac{3^n -1}{2}$
Uneven = Odd !
If there are $x_n$ words of length $n$ with an odd number of $a$'s then there are $3^n-x_n$ words of length $n$ with an even number of $a$'s.
To form words of length $n+1$ (with an odd number of $a$'s) we can EITHER add $b$ or $c$ to the $x_n$ OR we can add $a$ to the words with an even number of $a$'s.
So the recurruence for $x_{n+1}$ is ...