Numbers of sequence of $1's$ and $2's$ whose sum is $N$ , with evenly many $2's$ .

Question

Could someone finding the recurrence relation of this problem? Problem states below:

Write a recurrence for the sequence(order matters!) of $1's$ and $2's$ whose sum(adding up all the term of sequence) is $N$ , with evenly many $2's$ .

the solution on the book is given by :

$S(0) = 1$

$S(1) = 1$

$S(n) = S(n-1)+ F(n-1)-S(n-2)$

where $F(n)$ is the Fibonacci sequence of $n$th term , $S(n)$ is the summation of sequence, How to get this ,and where is the $F(n)$ comes from ?

Answer 1

In this case, I recommend finding three series in parallel.

Let $T(n)$ be the total number of sequences of $1$'s and $2$'s whose sum is $n$.

Let $E(n)$ be the number of sequences of $1$'s and $2$'s whose sum is $n$ with an even number of $2$'s.

Let $O(n)$ be the number of sequences of $1$'s and $2$'s whose sum is $n$ with an odd number of $2$'s.

Recognize that $T(n)=E(n)+O(n)$ and so $O(n)=T(n)-E(n)$ and recognize that the problem is asking us to find $E(n)$.

---

From an earlier example, we know that $T(0)=1, T(1)=1$ and $T(n)=T(n-1)+T(n-2)$ follows the Fibonacci series relation but is offset by one. That is, $T(n)=F(n+1)$. (Remember that $F(0)=0, F(1)=1, F(2)=1$)

This can be seen by the fact that any sequence which has summation $n$ either begins with a sequence of length $(n-1)$ and ends with a $1$ or begins with a sequence of length $(n-2)$ and ends with a $2$.

---

Now, for a sequence with an even number of $2$'s whose summation is $n$, one of two things will occur:

• It begins with a sequence whose summation is $n-1$ with an even number of $2$'s and it ends with a $1$
• It begins with a sequence whose summation is $n-2$ with an odd number of $2$'s and it ends with a $2$

There are $E(n-1)$ possibilities in the first case and there are $O(n-2)$ possibilities in the second case.

This gives us the relation:

$$E(n) = E(n-1)+O(n-2)$$

We don't want to have our final answer referring to the sequence $O(n)$ however, so let us rewrite it knowing that $O(n)=T(n)-E(n)$ and that $T(n)=F(n+1)$

$$E(n) = E(n-1)+F(n-1)-E(n-2)$$

We finally note that $E(0)=1$ and $E(1)=1$ as initial conditions since the empty sequence is the only valid sequence for $n=0$ and the sequence (1) is the only valid sequence for $n=1$.

This matches the form given in the problem statement (only difference being they used the letter $S$ instead of $E$).