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.
Best Answer
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