What is a recurrence relation for the number of sequences of yellow and purple stones of length N, where each sequence has the property that no two adjacent stones are purple.

Question

Piosellisf · Accepted Answer

So,we have to find a recurrence relation for the number of sequences of yellow and purple stones of length N, where, each sequence has the property that no two adjacent stones are purple.    Let aN be the number of such sequences of length N.    There are two cases:    1) The last stone is yellow.    In this case, the first n−1 stones must not have 2 adjacent purples.    Thus, there are aN−1 such sequences.    2)The last stone is purple.    In this case, the last 2 stones must be yellow and purple. So, the first N−2 stones must not have 2 adjacent purples.    Thus, there are aN−2 such sequences.    In total, there are aN−1+aN−2 sequences.    Therefore, aN=aN−1+aN−2, here, a0=1, a1=2. Hence, the required recurrence relation is aN=aN−1+aN−2

What is a recurrence relation for the number of sequences

Answered question

Answer & Explanation

New Questions in Algebra I