# 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.

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

### 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}}}$$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://plainmath.net/51608/what-is-a-recurrence-relation-for-the-number-of-sequences", "fetch_time": 1642405952000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2022-05/segments/1642320300343.4/warc/CC-MAIN-20220117061125-20220117091125-00507.warc.gz", "warc_record_offset": 464230479, "warc_record_length": 7955, "token_count": 460, "char_count": 1567, "score": 4.28125, "int_score": 4, "crawl": "CC-MAIN-2022-05", "snapshot_type": "latest", "language": "en", "language_score": 0.8433597683906555, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00018-of-00064.parquet"}