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.
 A: 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)$
A: If you are interested in a turn-the-crank approach for problems like this one, you might consider the method of generating functions-- more specifically, in this case, exponential generating functions (EGFs).  For your problem, let's define 
$$f(z) = \sum_{n=0}^{\infty} \frac{1}{n!} c_n {z^n}$$
We say $f(z)$ is the EGF of the sequence $c_n$.
The EGF for a sequence of 2s, 3s, or 4s, since we can have any number of those digits,  is 
$$1 + z + \frac{1}{2!} z^2 + \frac{1}{3!} z^3 + \dots = e^z$$
The EGF for a sequence of 1s, since only even multiples are allowed, is
$$1 + \frac{1}{2!} z^2 + \frac{1}{4!} z^4 + \dots = (1/2) (e^z + e^{-z})$$
The EGF of the possible permutations involving 1s, 2s, 3s, and 4s is simply the product of the EGFs of the component sequences, so
$$f(z) = (e^z)^3 \cdot (1/2) (e^z + e^{-z}) = (1/2) (e^{4z} + e^{2z})$$
Usually we want a closed form expression for $c_n$, which we can now get easily by expanding the series in the EGF:
$$f(z) = \frac{1}{2} \left( \sum_{n=0}^{\infty} \frac{1}{n!} 4^n z^n + \sum_{n=0}^{\infty} \frac{1}{n!} 2^n z^n \right)$$
$c_n$ is the coefficient of $z^n / n!$ in this series, i.e.
$$c_n = (1/2) (4^n + 2^n)$$
It's also possible to derive your recurrence from the EGF, but that's probably more trouble than it's worth, given that we have now have a formula for the number of acceptable sequences.
You can find introductions to generating functions in many books on combinatorics.  One that is available on-line is generatingfunctionology by Wilf:
www.math.upenn.edu/~wilf/DownldGF.html
A: Call the number of sequences of length $n$ with an even number of digits $e_n$, and similarly $o_n$ the odd ones. Then $e_0 = 1$, $o_0 = 0$.
You can construct an even of length $n + 1$ by adding 2, 3, 4 (3 options) to an even of length $n$, or a 1 to an odd of length $n$. Similarly, you can construct an odd of length $n+1$ out of sequences of length $n$. This allows to write:
\begin{align}
e_{n + 1}
  &= 3 e_n + o_n \\
o_{n + 1}
  &= e_n + 3 o_n
\end{align}
Write $o_n = e_{n + 1} - 3 e_n$ and $e_n = o_{n + 1} - 3 o_n$, substitute in the other equation:
\begin{align}
3 e_{n + 1} 
  &= 3 (o_{n + 1} - 3 o_n) + o_n \\
  &= 3 o_{n + 1} - 6 o_n \\
3 o_{n + 1}
  &= 3 e_n +  3 (e_{n + 1} - 3 e_n) \\
  &= 3 e_{n + 1} - 6 e_n 
\end{align}
Shift the original system by one, and substitute the above, you get:
$$
e_{n + 2} = 6 e_{n + 1} - 7 e_n
$$
Using your initial values (or counting directly) $e_0 = 1$, $e_1 = 3$.
Need to solve this. Define $E(z) = \sum_{n \ge 0} e_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get:
$$
\frac{E(z) - e_0 - e_1 z}{z^2}
  = 6 \frac{E(z) - e_0}{z} - 7 E(z)
$$
The solution to this, written as partial fractions, is:
$$
E(z) = \frac{1}{2} \cdot \frac{1}{1 + z} + \frac{1}{2} \cdot \frac{1}{1 - 7 z}
$$
This is just two geometric series:
$$
e_n = \frac{7^n + (-1)^n}{2}
$$
