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)

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.$  
