Joyce Smith

2022-01-06

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.

Piosellisf

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 ${a}_{N}$ 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 ${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 $N-2$ stones must not have 2 adjacent purples.
Thus, there are ${a}_{N-2}$ such sequences.
In total, there are ${a}_{N-1}+{a}_{N-2}$ sequences.
Therefore, ${a}_{N}={a}_{N-1}+{a}_{N-2}$, here, ${a}_{0}=1$, ${a}_{1}=2$. Hence, the required recurrence relation is ${a}_{N}={a}_{N-1}+{a}_{N-2}$

Do you have a similar question?