Problem: How many strings are there of length $ n $ over $ \{ 1,2,3,4,5,6 \} $ s.t. the sum of all characters in the string divide by $ 3 $.
Attempt:
Initially I thought about solving this using generating functions ( $ (x^0 + x^3 +...)^n = (\frac{1}{1-x^3})^n $ ), but that is little bit problematic since we don't have an equation equal to some number and maybe this way is too difficult.
Then I thought about using recurrence relation and I done like this:
Let $ a_n $ denote the number of strings of length $ n $ s.t. the sum of all characters in the string divide by $ 3 $. Let's look at the first character, if it divides by 3 then there are two choices - $ 3,6 $ and the rest of the $ n-1 $ string is legal, similarly if the first character does not divide by 3 then there are four choices - $ 1,2,4,5 $ and the rest of the $ n-1 $ string is legal, so we have the recurrence relation $ a_n = a_{n-1} + a_{n-1} = 2*a_{n-1} $.
Obviously this recurrence relation is wrong but why? I keep repeating mistakes like this when creating recurrence relations, and I'd like to know where my mistake is here. ( besides having wrong values for different $ n $, where was the fallacy in logic that led me to the creation of this recurrence relation? maybe is it that if the first character is from $\{ 3,6 \} $ then the rest of the string is not necessarily legal? ).
Your recurrence is wrong because the $a$s on the right are not necessarily strings that sum to a multiple of $3$. You can follow this approach, but you need to let $b_n$ be the number of strings that sum to a number equivalent to $1 \bmod 3$ and $c_n$ be the number of strings that sum to a number equivalent to $2 \bmod 3$. Then you have a coupled set of recurrences. We have $$a_n=2a_{n-1}+2b_{n-1}+2c_{n-1}\\b_n=2a_{n-1}+2b_{n-1}+2c_{n-1}\\ c_n=2a_{n-1}+2b_{n-1}+2c_{n-1}\\a_0=1,b_0=0,c_0=0$$ Because of the symmetry, after $a_0$ all three sequences are equal. As there are $6^n$ total strings, there are $\frac 13\cdot 6^n$ that sum to a multiple of $3$.