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.