Fibonacci sequence emerging from integer partitioning Let $a_n$ count the number of ways a sequence of $1$s and $2$s will sum to n. 
For example $a_3 = 3$ since $1 + 1 + 1 = 3 = 1 + 2 = 3 = 2 + 1 = 3$ 
(The ordering matters so  1 + 2 is different from 2 + 1).

Find $a_4$ and $a_5$

I think that
$a_4 = 5$ since $$1 + 1 + 1 + 1 = 2 + 2 = 1 + 1 + 2 =  1 + 2 + 1 = 2 + 1 + 1$$
and $a_5 =8$ since $$1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 2 = 1 + 2 + 2 = 1 + 1 + 1 + 2 = 1 + 1 + 2 + 1 = 1 + 2 + 1+ 1= 2 + 1 + 1 + 1$$
Now the pattern is emerging, $a_3 + a_4 = a_5$ because $3 + 5 = 8$

Now I want to give a recurrence relation for $a_n$ with initial
  conditions.

So I would say that $$a_n = a_{n-1} + a_{n-2}$$, It is basically the fibonacci sequence ?
and $a_2 =2$ since $1 + 1 = 2$
and $a_1 = 1$
So the initial conditions is what then ? $a_1 =1$ and $a_2 = 2$ ??

I think your conjecture is correct, but we need to give an induction proof. 
So suppose your result is true for $k = 1, 2, \ldots, n$, where $n > 1$. We need to show that $a_{n+1} = a_n + a_{n-1}.$
Now $a_{n+1}$ denotes the number of sequences of $1$s and $2$s that add up to $n+1$. 
Each sequence of $1$s and $2$s that adds either to $n$ or to $n-1$ yields a similar sequence that adds to $n+1$ by the adjunction of a $1$ or a $2$, respectively, at the end. So we must have 
$$a_{n}+a_{n-1} \leq a_{n+1}.$$
On the other hand, if a sequence of $1$s and $2$s adds to $n+1$, then we can delete the final term of this sequence, which is either a $1$ or a $2$, to obtain a sequence adding either to $n$ or to $n-1$. So we must have 
$$a_{n+1} \leq a_n + a_{n-1}.$$
The last two inequalities give our desired equality. 
