2

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$ ??

alkabary
  • 6,214
  • Note that the first term of the sum is either $1$ or $2$ and consider what happens when you delete it. – Mark Bennet Nov 23 '15 at 17:47
  • You can either start at $a_1=1$ and $a_2=2$, or start at $a_0=1$ and $a_1=1$. Some people might regard this as an offset of one position from the Fibonacci sequence, which typically starts with $a_0=0, a_1=1, a_2=1$. – Henry Nov 23 '15 at 17:49
  • @Henry but basically what I have is right ? and $a_0=1$ doesn't make sense ? It should be that $a_0 = 0$ right because there is no ways that we can write $0$ as a sum of ones and twos – alkabary Nov 23 '15 at 17:51
  • alkabary: basically what you have looks reasonable to me. But $0$ can be written as the empty sum of $1$s and $2$s in exactly one way. – Henry Nov 23 '15 at 17:54

1 Answers1

3

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.

Saaqib Mahmood
  • 26,762