What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$ What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$?
I have tried to answer it as recursion formula in the following logic:
In order to build $ A(n) $, I will split into several cases:


*

*if the string starts with $a$, then I will need another $a$ to make an even number of $a's$. so we get $aa[A(n-2)]$ meaning 2 $a's$ at the start + a valid string at the size of $n-2$.

*if it starts with $b,c,d$ we get $b[A(n-1)]$ + $c[A(n-1)]$ +$d[A(n-1)]$, meaning a one of the letters + a valid string at the size of $n-1$.


So we will get a recursion formula that looks like that:
$A(n) = A(n-2) + 3A(n-1)$
I'm not 100% on my answer, am I right to approach it in that direction?    
 A: That's close.  Consider an $n$-letter word with an even number of A's.  There are two cases:


*

*If the last character is not an A, then removing it gives an $n-1$ letter word with an even number of A's.  Since there are 3 possibilities for the last letter (B, C, D), this accounts for $3A(n-1)$ cases.

*If the last character is an A, then removing it gives an $n-1$ letter word with an odd number of A's.  There are clearly $4^{n-1}-A(n-1)$ of those.
That gives us $A(n)=3A(n-1)+4^{n-1}-A(n-1)=4^{n-1}+2A(n-1)$, and we have to toss in a base case of $A(1)=3$.
A: Consider two cases.
Case 1.  The string is all $c$'s and $d$'s. There are $2^n$ such strings, and each of them has an even number of $a$'s, namely zero.
Case 2. The string is not all $c$'s and $d$'s. There are $4^n-2^n$ such strings, and exactly half of them, that is $\frac{4^n-2^n}2$, have an even number of $a$'s. (Why? Find the leftmost letter which is not $c$ or $d$, and flip it from $a$ to $b$ or from $b$ to $a$, thus changing the parity of the number of $a$'s.)
So the answer is $2^n+\frac{4^n-2^n}2=\boxed{\frac{4^n+2^n}2}=\boxed{2^{n-1}(2^n+1)}=$ A007582.
More generally, for strings over a $k$-letter alphabet, the number of strings of length $n$ in which a specified letter occurs an even number of times is
$$\frac{k^n+(k-2)^n}2.$$
P.S. More detailed explanation of Case 2, as requested in a comment.
Let $S$ be the set of all strings (of length $n$) which are not all $c$'s and $d$'s; so $|S|=4^n-2^n$. Partition $S$ into two subsets $D$ and $E$, where $D$ is the set of all strings in $S$ with an odd number of $a$'s, and $E$ is the set of all strings in $S$ with an even number of $a$'s.
Define a map $f:S\to S$ as follows. Given a string $x\in S$, find the first letter in $x$ (reading from left to right) which is not a $c$ or a $d$; if it's an $a$ change it to $b$; if it's a $b$ change it to $a$. For example, $f(cadb)=cbdb$, $f(cbdb)=cadb$. Note that $f$ is an involution ($f(f(x))=x$), and $f$ swaps $D$ and $E$, i.e., $f(D)=E$ and $f(E)=D$. It follows that $|D|=|E|$ and so $|E|=\frac{|S|}2=\frac{4^n-2^n}2$, and the total number of strings with an even number of $a$'s is $2^n+|E|=\frac{4^n+2^n}2$.
Let $R$ be the set of all strings which are all $b$'s, $c$'s, and $d$'s, and contain at least one $b$; so $|R|=3^n-2^n$ and $R\subseteq E\subseteq S$. (The set $R$ plays no special role in my argument, but a commenter was asking about it.) The involution $f$ pairs elements of $R$ with strings in $D$ which contain exactly one $a$ and the $a$ precedes all the $b$'s; for example, if $n=4$, then $cbdb$ is paired with $cadb$.
A: A systematic approach is to form the finite state automaton of the strings you accept:

Then, for all possible $n$ we have the number of strings of that length that end up each state described by repeating the transition matrix $n$ times for our finite state automaton $F$:
$$F(n) = \begin{bmatrix}
3 &1\\
1 &3\\
\end{bmatrix}^n\begin{bmatrix}
1\\0
\end{bmatrix}$$
The above matrix can be diagonalized:
$$F(n) = \frac{1}{2}\begin{bmatrix}
-1 &1\\
1 &1\\
\end{bmatrix}\begin{bmatrix}
2 &0\\
0 &4\\
\end{bmatrix}^n\begin{bmatrix}
-1 &1\\
1 &1\\
\end{bmatrix}\begin{bmatrix}
1\\0
\end{bmatrix}$$
And simplified:
$$F(n) = \frac{1}{2}\begin{bmatrix}
-1 &1\\
1 &1\\
\end{bmatrix}\begin{bmatrix}
2^n &0\\
0 &4^n\\
\end{bmatrix}\begin{bmatrix}
-1\\1
\end{bmatrix}$$
$$F(n) = \frac{1}{2}\begin{bmatrix}
-1 &1\\
1 &1\\
\end{bmatrix}\begin{bmatrix}
-2^n\\
4^n\end{bmatrix}$$
$$F(n) = \frac{1}{2}\begin{bmatrix}
4^n + 2^n\\
4^n - 2^n\end{bmatrix}$$
Since we are interested in the number of even strings, we have:
$$A(n) = F(n) \begin{bmatrix}1&0\end{bmatrix} = \frac{1}{2}(4^n + 2^n)$$
