Number of sequences with n digits, even number of 1's ASKED: 
Let $c_n$ be the number of sequences with $n$ digits from $\{1,2,3,4\} $ with an even number of $1's$. 
Determine $c_n$ for $n \geq 0$.
GIVEN RESULT:
$c_{n+1} = 3 \cdot c_n + 1 \cdot (4^n-c_n) \Rightarrow c_{n+1} = 2 \cdot c_n + 4^n$
and  from this $c_n$ can be solved.
MY RESULT
My problem with this question is that I don't get how to come to the result: $c_{n+1} = 3 \cdot c_n + 1 \cdot (4^n-c_n) $
My current reasoning is as follows:
$c_{n+1}$ will have one more slot than $c_n$. Since $c_1 = 3$, this means that there are $3 \cdot c_n$ more possibilities for $c_{n+1}$. Also, because $n$ can be either even or uneven, we need to incorporate the number of possibilities that now 'become available' if $n+1$ is an even number and $n$ was not. This is done by adding $(4^n-c_n)$ to the equation such that the final (intermediate step) equation becomes: $c_{n+1} = 3 \cdot c_n + 1 \cdot (4^n-c_n) $. Writing this out gives $c_{n+1} = 2 \cdot c_n + 4^n$.
Note that I came up with this reasoning after looking at the answer. Now this question is supposed to be linked to combinatorics so I think there is a more structural and mathematic approach to this question (instead of reasoning). I am curious to what this approach might be.
So what I'm looking for is either a very structural approach to solving these kind of questions or a combinatorial approach to this question.
Thanks in advance. I will be actively commenting if needed.

If the number of sequence of $n$ numbers with even number of one is $c_n$ then the number of sequences of $n$  numbers with odd number of ones is $4^n-c_n$
Number of sequence of $n+1$ numbers with even number of ones either contains $1$ or it contains any other number except one as the last number. Number of sequence of $n+1$ numbers having $1$ as the last number must have odd number of $1$ s among their first n numbers. And the number of sequence of $n$ numbers with  odd number of ones is $4^n-c_n$. So the number of sequence of $n+1$ numbers having $1$ as the last number is $4^n-c_n$
Number of sequence of $n+1$ numbers with even number of ones having $2,3,4$ as the last number must have even number of ones among their first $n $ terms. And the number of sequence of $n$ numbers with even number of ones is $c_n$. The $n+1$th term of this sequence can be $2,3,4$ so this number must be multiplied by $3$. Giving us the total number of sequence of $n+1$ numbers with even number of ones having $2,3,4$ as the last number as $3c_n$
So we have $c_{n+1}=3c_n+(4^n-c_n)$
