# What is a recurrence relation for the number of sequences

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.

• Questions are typically answered in as fast as 30 minutes

### Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

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