Help with this problem

[static timber]

Problem Statement: A binary sequence is a sequence in which each term is 0 or 1. Determine a recurrence relation for the number of binary sequences of length n that do not contain two adjacent 1s, then find a simple expression for this number.

[harsh heath]

if all sequences end in 0 or 1, then you can create a new sequence by taking an old one and adding either a 1 or a 0. if there cannot be any touching 1's then you'll need to know if your sequence ends in a 1 or 0, so lets say we do, I(n) will be the total number of sequences of length n ending in a 1 with no adjacent 1's and O(n) is the same but ends in 0. then the total sequences with no adjacent 1's is just I(n)+O(n), the total regardless of ending. adding a new term to each sequence would get us a recurrence for each that we can probably use to get a recurrence for the total overall. adding a new term to a sequence ending in 0 is simple, the new term could be 1 or 0, but that would naturally change the ending, so lets say we want to add a 1, then our sequence is 1 longer and it ends in a 1, but because we cant have adjacent 1's, the rest of the sequence cannot end in a 1 so all possible sequences, I(1+n) = O(n). if we added a 0 then the rest of the sequence could have ended in anything so, O(1+n) = I(n) + O(n). those are both recurrence relations that can be converted into only 1 if we assume that the answer to our question is C(n) which would be C(n)=I(n)+O(n), then trying to rewrite our recurrences in terms of C we get C(n+1) = C(n)+C(n-1). i hope this helps. feel free to reply if you would like more help working the recurrence itself.

[vagrant inlet]

Let f(n) be the number of binary sequences of length n which does not contain any adjacent 1s. Then we can split it into 2 cases:
1) The n-th term is 0
In this case the number of sequences is
just simply f(n-1) by taking the number
of sequences of length n-1 and adding a 0
at the last.
2) The n-th term is 1
In this case the n-1 th term must be 0 to
avoid having adjacent 1s. Thus we can
ignore the last 2 terms and so the number
of sequences is f(n-2) by taking the
number sequences of length n-2 and
adding 01 as the last 2 terms.
By combining the number of sequences of both cases we conclude that:

              **f(n) = f(n-1) + f(n-2)**

[static timber]

@vagrant inlet and @harsh heath thanks for helping, I finally understood the problem

!done

[trail raptor]

If you are done with this channel, please mark your problem as solved by typing .close

[static timber]

.close