Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which turns out to be: $$\frac{4^n+2^n}{2}$$However, the question was only answered properly through a generating function method, which, whilst I love the idea of it, is a tad bit too complex for me.
How does one create a recurrence relation for this problem?
Thanks in advance.
Edit 1
To visualise what I'm looking for:
$a_0 = |\{\}| = 0$
$a_1 = |\{2,3,4\}| = 3$
$a_2 = |\{11,22,33,24,32,33,34,42,43,44\}| = 10$
$a_3 = 36$
I don't suppose one would be able to notice a pattern from this? Or deduct one?
You can create $n+1$ digits number just by 'adding' one number as the left-most digit to $n$ digits number. (For example, you can create $1312$ by adding $1$ as the left most digit to $312$.)
Case 1 : If the number of $1$'s is odd in a $n$ digits number, then you need to add $1$ as the left most digit of a new $n+1$ digits number. So, in this case, you have $$(4^n-c_n)\cdot 1\ \ \text{(cases)}.$$
Case 2 : If the number of $1$'s is even in a $n$ digits number, then you need to add $2,3,\text{or}\ 4$ as the left most digit of a new $n+1$ digits number. So, in this case, you have $$c_n\cdot 3\ \ \text{(cases)}.$$
Hence, you'll have $$c_{n+1}=(4^n-c_n)\cdot 1+c_n\cdot 3.$$