For all $n\in\mathbb{N}$, let $a_n$ denote the number of strings of length $n$ over $\{1,2,3,4\}$ such that: 
For all $n\in\mathbb{N}$, let $a_n$ denote the number of strings of length $n$ over $\{1,2,3,4\}$ in which all of the even digits appear before the odd digits, and digit 1 appears exactly once.
Compute: $a_4$ and $a_{2015}$

Hey everyone. I've tried thinking about small cases, for example when $n=3$. In that case $a_3=11$. I thought about solving it using a recurrence relation but I don't know how to compose it. I tried defining $b_n$- number of strings of length $n$ as required that end with a 3. $c_n$- number of strings of length $n$ as required that end with 1. $d_n$- number of strings of length $n$ as required, without any odd digits, and so $a_n=b_n+c_n+d_n$... But I don't think this is the right way.
I would love to get some help on that question. Thanks in advance :)
Edit: could it be solved using the binomial theorem?
 A: I am not sure if I interpreted the question right (correct me if I'm wrong), but for $n=3$ I have $a_3 = 11$.
Using a different approach, given a string of length $n$. Since there are 2 even digits, there are $2^k$ ways to arrange the first $k$ letters of the string (where $k=0,...,n-1$, since each string has a single $1$-digit).
For the odd string section (where we now have $n-k$ letters left to fill in), there are $(n-k)$ ways to do this, since we can select one position out of $n-k$ unfilled letters to be the $1$-digit, and then fill the rest to be the digit $3$.
Thus, we have:
$$a_n = \sum_{k=0}^{n-1} 2^k (n-k)$$
Using the Geometric sum formula (and differentiating the formula to find the closed form of $\sum {k2^k}$) we have:
$$a_n = 2^{n+1} - (n+2)$$
So we have $a_4 = 26$ and $a_{2015} = 2^{2016} - 2017$.

To find a possible recurrence relation (which I don't have a interpretation for right now), we can use generating functions, where if we let $A(x) = \sum_{n\geq 0} a_n x^n$ we have:
$$\begin{align} A(x) &= \frac{2}{1-2x} - \frac{x}{(1-x)^2} - \frac{2}{1-x} \\ &= 
\frac{x}{(1-x)^2 (1-2x)} \end{align}$$
If we log both sides, differentiate and then multiply both sides by $x$, we have:
$$\frac{x A'(x)}{A(x)} = \frac{\sum_{n\geq 0} n a_n x^n}{\sum_{n\geq 0} a_n x^n}  = 1 + \frac{2}{1-2x} + \frac{2}{1-x}$$
$$\sum_{n\geq 0} n a_n x^n  = \left(1 + \frac{2}{1-2x} + \frac{2}{1-x}\right) \sum_{n\geq 0} a_n x^n \tag{1}$$
Equating the coefficients on both sides of $(1)$ we have the recurrence:
$$a_n = \frac{2}{n-1} \sum_{k=1}^{n-1} (2^{k-1} + 1)a_{n-k}$$
Where we take $a_1 =1$ and $a_0 = 0$.
