What is a recurrence relation for the number of sequences

Joyce Smith 2022-01-06 Answered
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.

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Expert Answer

Piosellisf
Answered 2022-01-07 Author has 3607 answers
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}}}\)
Not exactly what you’re looking for?
Ask My Question
0
 

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more
...