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

Write a recurrence for the sequence(order matters!) of 1′s1’s and 2′s2’s whose sum(adding up all the term of sequence) is NN , with evenly many 2′s2’s .

the solution on the book is given by :

S(0)=1S(0) = 1

S(1)=1S(1) = 1

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

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

=================

When you say “sum” do you mean that the terms add to NN? So…there aren’t any at all if the length exceeds NN?

– lulu

2 days ago

Hint: One property of the Fibonacci numbers is that F(n)F(n) is the number of finite sequences of 11 and 22 with sum n−1n-1.

– Henning Makholm

2 days ago

@lulu you understanding is correct

– PSY

2 days ago

=================

1 Answer

1

=================

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

Let T(n)T(n) be the total number of sequences of 11’s and 22’s whose sum is nn.

Let E(n)E(n) be the number of sequences of 11’s and 22’s whose sum is nn with an even number of 22’s.

Let O(n)O(n) be the number of sequences of 11’s and 22’s whose sum is nn with an odd number of 22’s.

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

From an earlier example, we know that T(0)=1,T(1)=1T(0)=1, T(1)=1 and T(n)=T(n−1)+T(n−2)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)T(n)=F(n+1). (Remember that F(0)=0,F(1)=1,F(2)=1F(0)=0, F(1)=1, F(2)=1)

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

Now, for a sequence with an even number of 22’s whose summation is nn, one of two things will occur:

It begins with a sequence whose summation is n−1n-1 with an even number of 22’s and it ends with a 11

It begins with a sequence whose summation is n−2n-2 with an odd number of 22’s and it ends with a 22

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

This gives us the relation:

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

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

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

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

This matches the form given in the problem statement (only difference being they used the letter SS instead of EE).