Recursion relation and initial conditions Write a recursion relation and initial conditions for the number of words of length n using the letters A,B,C  such that the number of the letter 'A' is even. 
(A occur an even number of times)
 A: Let $F(n)$ be the number of words of size $n$ over $A,B,C$ that contain even number of $A$s.
consider the first letter:


*

*if its $B,C$ then the remainder of the word (i.e. $n-1$ subword) have even number of $A$s, and that number is $F(n-1)$, Therfore those scenarios add $$2F(n-1)$$

*If it's $A$, then the remainder have odd number of $A$s, and since every word have either odd or even number of $A$s by using the complement we get that the option for the remainder is $$3^{n-1}-F(n-1)$$


So we got $$F(n) =2F(n-1) + 3^{n-1} - F(n-1) = 3^{n-1} + F(n-1)$$
and the initial condition $ F(0) = 1 $ (since there is only $1$ option to build a word of length $0$ with even number of $A$s, which is the empty word) 
A: $o_{n}=$ number of words having $n$ letters and with odd number of
letter $A$
$e_{n}=$ number of words having $n$ letters and with even number
of letter $A$
Then $o_{0}=0$ and $e_{0}=1$ (empty word counts).
$o_{n+1}=2o_{n}+e_{n}$
$e_{n+1}=o_{n}+2e_{n}$
Then $o_{n}+e_{n}=3^{n}$ leads to $e_{n+1}=3^{n}+e_{n}$
A: Hint:
You can add an 'A' to a string with an odd number of 'A's, or you can add a 'B' or a 'C' to a string with an even number of 'A's.
The number of strings with an odd number of 'A's can be found directly from the number of strings with an even number of 'A's.
A: Let $a_n$ be the number of such words.
Clearly
$a_0=1$ (because there is no such word)
$a_1=2$ (words are B,C)
$a_2=5$ (words are AA, BB, BC, CB, CC).
$a_3=14$
(words are AAB, ABA, BAA, AAC, ACA, CAA, BBB, BBC, BCB, CBB, CCB, CBC, BCC, CCC) 
Note that $$a_{n+2}=4a_{n+1}-3a_n.$$ for all $n=0,1,2,3,4,...$
FOR:
consider the last letter of any word with length $n.$  
