How many $n$-digit numbers are there with no or even number of $1$s in them if only digits $1$, $2$, $3$ and $4$ are allowed?

Question

You are given an unlimited supply of each of the digits 1,2,3 or 4. Using only these four digits, you construct n digit numbers. Such n digit numbers will be called LEGITIMATE if it contains the digit 1 either an even number times or not at all. Number of n digit legitimate numbers are:-
My attempt:-
(1) if no 1 is present - $3^n$
(2) if 1 present 2times-${n\choose 2}.3^{n-2}$
(3)if 1 present 4times-${n\choose 4}.3^{n-4}$
And so on...
Hence, $3^n+3^{n-2}{n\choose2}+$...
Therefore $\frac{(3+1)^n}{2} =2^{2n-1}$ but the real ans is
$2^{n-1}(2^n+1)$, please tell complete solution.

Answer 1

You seem to be making what is often called a silly mistake.

Starting from the second term, every other term is missing from the series, compared to a usual binomial expansion. You didn't account for that.

$$\begin{align*} &3^n + 3^{n-2} \binom{n}{2} + 3^{n-4} \binom{n}{4} + \cdots \\[0.3cm] =\;&\frac{(3+1)^n + (3 - 1)^n}{2} \\[0.3cm] =\;& \frac{4^n + 2^n}{2} \\[0.3cm] =\;& 2^{n-1}(2^n + 1) \end{align*}$$

As pointed out by JMoravitz in the comments below, the last term in the series above would either be $3 \binom{n}{n-1}$ or $\binom{n}{n}$ depending on whether $n$ is even or odd.