ในทางคณิตศาสตร์ลำดับอนันต์ของจำนวน เรียกว่า ลำดับเวียน เกิดคงที่ (constant-recursive)ถ้ามันสอดคล้องกับสมการในรูปแบบ ${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{nd},}$$

สำหรับทุก ๆโดยที่เป็นค่าคงที่สมการนี้เรียกว่าความสัมพันธ์เวียนเกิดเชิงเส้นแนวคิดนี้ยังเป็นที่รู้จักในชื่อลำดับเวียนเกิดเชิงเส้นลำดับเวียนเกิดเชิงเส้นลำดับเวียนเกิดเชิงเส้นหรือลำดับ C- finite ^{[ 1 ]}${\displaystyle n\geq d}$${\displaystyle c_{i}}$

ตัวอย่างเช่นลำดับฟิโบนาชชี

${\displaystyle 0,1,1,2,3,5,8,13,\ldots }$,

เป็นลำดับเวียนเกิดคงที่เพราะเป็นไปตามความสัมพันธ์เวียนเกิดเชิงเส้นกล่าวคือ แต่ละจำนวนในลำดับเป็นผลรวมของสองจำนวนก่อนหน้า^{[ 2 ]} ตัวอย่างอื่นๆ ได้แก่ ลำดับ กำลังสองซึ่งแต่ละจำนวนเป็นผลรวมของสองเท่าของจำนวนก่อนหน้า และลำดับกำลังสอง ลำดับ เลขคณิต ทั้งหมดลำดับเรขาคณิตทั้งหมดและพหุนาม ทั้งหมด เป็นลำดับเวียนเกิดคงที่ อย่างไรก็ตาม ไม่ใช่ทุกลำดับจะเป็นลำดับเวียนเกิดคงที่ ตัวอย่างเช่นลำดับแฟกทอเรียลไม่ใช่ลำดับเวียนเกิดคงที่ ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle 1,2,4,8,16,\ldots }$${\displaystyle 0,1,4,9,16,25,\ldots }$${\displaystyle 1,1,2,6,24,120,\ldots }$

ลำดับเวียนเกิดคงที่ได้รับการศึกษาในสาขาคณิตศาสตร์เชิงการจัดเรียงและทฤษฎีผลต่างจำกัดนอกจากนี้ยังปรากฏในทฤษฎีจำนวนเชิงพีชคณิตเนื่องจากความสัมพันธ์ของลำดับกับรากพหุนามในการวิเคราะห์อัลกอริทึมเช่น เวลาในการทำงานของฟังก์ชันเวียนเกิด แบบง่าย และในทฤษฎีภาษาเชิงรูปธรรมซึ่งใช้ในการนับสตริงที่มีความยาวไม่เกินที่กำหนดในภาษาปกติลำดับเวียนเกิดคงที่ยังคงอยู่ภายใต้การดำเนินการทางคณิตศาสตร์ที่สำคัญ เช่นการบวกแบบพจน์ต่อพจน์การคูณแบบพจน์ต่อพจน์และผลคูณโคชี

ทฤษฎีบท สโกเลม-มาห์เลอร์-เลคกล่าวว่าค่าศูนย์ของลำดับเวียนเกิดคงที่นั้นมีรูปแบบที่ซ้ำกันอย่างสม่ำเสมอ (และในที่สุดจะกลายเป็นคาบ) ปัญหาของสโกเลมซึ่งถามถึงอัลกอริทึมที่จะตรวจสอบว่าความสัมพันธ์เวียนเกิดเชิงเส้นมีค่าศูนย์อย่างน้อยหนึ่งค่าหรือไม่นั้น เป็นปัญหาที่ยังหาคำตอบไม่ได้ในทางคณิตศาสตร์

ลำดับเวียนเกิดคงที่คือ ลำดับของจำนวนเต็มจำนวนตรรกยะจำนวนพีชคณิตจำนวนจริงหรือจำนวนเชิงซ้อน (เขียน ย่อว่า ) ที่สอดคล้องกับสูตรในรูปแบบ ${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$${\displaystyle (s_{n})_{n=0}^{\infty }}$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{nd}=\sum _{k=1}^{d}c_{k}s_{nk},}$$

สำหรับค่าสัมประสิทธิ์คงที่บาง ค่า ที่อยู่ในโดเมนเดียวกันกับลำดับ (จำนวนเต็ม จำนวนตรรกยะ จำนวนพีชคณิต จำนวนจริง หรือจำนวนเชิงซ้อน) สมการนี้เรียกว่าความสัมพันธ์เวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์คงที่อันดับdอันดับของลำดับคือจำนวนเต็มบวกที่เล็กที่สุดที่ทำให้ลำดับนั้นสอดคล้องกับความสัมพันธ์เวียนเกิดอันดับdหรือสำหรับลำดับที่เป็นศูนย์ทุกที่ ${\displaystyle n\geq d,}$${\displaystyle c_{1},c_{2},\dots ,c_{d}}$${\displaystyle d}$${\displaystyle d=0}$

คำจำกัดความข้างต้นอนุญาตให้ ลำดับ แบบคาบ ในที่สุด เช่นและผู้เขียนบางคนกำหนดให้ซึ่งไม่รวมลำดับดังกล่าว^{[ 3 ] [ 4 ] [ 5 ]}${\displaystyle 1,0,0,0,\ldots }$${\displaystyle 0,1,0,0,\ldots }$${\displaystyle c_{d}\neq 0}$

ตัวอย่างที่เลือกของลำดับการเรียกซ้ำคงที่จำนวนเต็ม^{[ 6 ]}

ชื่อ	คำสั่ง ( )${\displaystyle d}$	ค่าแรกๆ ไม่กี่ค่า	การเกิดซ้ำ (สำหรับ)${\displaystyle n\geq d}$	ฟังก์ชันการสร้าง	โออีไอเอส
ลำดับศูนย์	0	0, 0, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {0}{1}}}$	เอ000004
ลำดับหนึ่ง	1	1, 1, 1, 1, 1, 1, ...	${\displaystyle s_{n}=s_{n-1}}$	${\displaystyle {\frac {1}{1-x}}}$	A000012
หน้าที่เฉพาะของ${\displaystyle \{0\}}$	1	1, 0, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {1}{1}}}$	เอ000007
เลขยกกำลังสอง	1	1, 2, 4, 8, 16, 32, ...	${\displaystyle s_{n}=2s_{n-1}}$	${\displaystyle {\frac {1}{1-2x}}}$	A000079
เลขยกกำลังของ −1	1	1, −1, 1, −1, 1, −1, ...	${\displaystyle s_{n}=-s_{n-1}}$	${\displaystyle {\frac {1}{1+x}}}$	A033999
หน้าที่เฉพาะของ${\displaystyle \{1\}}$	2	0, 1, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {x}{1}}}$	A063524
การขยายทศนิยมของ 1/6	2	1, 6, 6, 6, 6, 6, ...	${\displaystyle s_{n}=s_{n-1}}$	${\displaystyle {\frac {1+5x}{1-x}}}$	A020793
การขยายทศนิยมของ 1/11	2	0, 9, 0, 9, 0, 9, ...	${\displaystyle s_{n}=s_{n-2}}$	${\displaystyle {\frac {9x}{1-x^{2}}}}$	A010680
จำนวนเต็มที่ไม่เป็นลบ	2	0, 1, 2, 3, 4, 5, ...	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {x}{(1-x)^{2}}}}$	A001477
จำนวนเต็มบวกคี่	2	1, 3, 5, 7, 9, 11, ...	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {1+x}{(1-x)^{2}}}}$	A005408
เลขฟิโบนาชชี	2	0, 1, 1, 2, 3, 5, 8, 13, ...	${\displaystyle s_{n}=s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {x}{1-xx^{2}}}}$	A000045
หมายเลขลูคัส	2	2, 1, 3, 4, 7, 11, 18, 29, ...	${\displaystyle s_{n}=s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {2-x}{1-xx^{2}}}}$	A000032
หมายเลขเพลล์	2	0, 1, 2, 5, 12, 29, 70, ...	${\displaystyle s_{n}=2s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {x}{1-2x-x^{2}}}}$	A000129
เลขยกกำลังสองสลับกับเลขศูนย์	2	1, 0, 2, 0, 4, 0, 8, 0, ...	${\displaystyle s_{n}=2s_{n-2}}$	${\displaystyle {\frac {1}{1-2x^{2}}}}$	A077957
ส่วนกลับของพหุนามไซโคลโทมิก ที่ 6	2	1, 1, 0, −1, −1, 0, 1, 1, ...	${\displaystyle s_{n}=s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {1}{1-x+x^{2}}}}$	A010892
จำนวนสามเหลี่ยม	3	0, 1, 3, 6, 10, 15, 21, ...	${\displaystyle s_{n}=3s_{n-1}-3s_{n-2}+s_{n-3}}$	${\displaystyle {\frac {x}{(1-x)^{3}}}}$	A000217

ลำดับ 0, 1, 1, 2, 3, 5, 8, 13, ... ของจำนวนฟิโบนาชชีเป็นลำดับเวียนเกิดคงที่อันดับ 2 เนื่องจากเป็นไปตามความสัมพันธ์เวียนเกิดที่มีตัวอย่างเช่นและลำดับ 2, 1, 3, 4, 7, 11, ... ของจำนวนลูคัสเป็นไปตามความสัมพันธ์เวียนเกิดเดียวกันกับลำดับฟิโบนาชชี แต่มีเงื่อนไขเริ่มต้นเป็นและโดยทั่วไปแล้วลำดับลูคัส ทุกลำดับ เป็นลำดับเวียนเกิดคงที่อันดับ 2 ^{[ 2 ]}${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle F_{0}=0,F_{1}=1}$${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$${\displaystyle F_{6}=F_{5}+F_{4}=5+3=8}$${\displaystyle L_{0}=2}$${\displaystyle L_{1}=1}$

สำหรับค่าใดๆ ของและค่าใดๆลำดับเลขคณิตจะเป็นลำดับเวียนเกิดคงที่อันดับ 2 เนื่องจากสอดคล้องกับเงื่อนไขเมื่อพิจารณาในภาพรวมแล้ว โปรดดูที่ลำดับพหุนามด้านล่าง ${\displaystyle a}$${\displaystyle r\neq 0}$${\displaystyle a,a+r,a+2r,\ldots }$${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$

สำหรับค่าใดๆ ของและลำดับเรขาคณิตจะเป็นลำดับเวียนเกิดคงที่อันดับ 1 เนื่องจากเป็นไปตามเงื่อนไขซึ่งรวมถึงลำดับ 1, 2, 4, 8, 16, ... รวมถึงลำดับจำนวนตรรกยะด้วย ${\displaystyle a\neq 0}$${\displaystyle r}$${\displaystyle a,ar,ar^{2},\ldots }$${\displaystyle s_{n}=rs_{n-1}}$${\textstyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...}$

ลำดับที่ในที่สุดจะเป็นคาบที่มีความยาวคาบเท่ากับค่าคงที่เรียกว่าลำดับเวียนเกิด เนื่องจากลำดับนี้สอดคล้องกับเงื่อนไขสำหรับทุกค่าn โดยที่ลำดับคือความยาวของส่วนเริ่มต้นรวมถึงบล็อกที่ซ้ำกันบล็อกแรก ตัวอย่างของลำดับดังกล่าวได้แก่ 1, 0, 0, 0, ... (ลำดับที่ 1) และ 1, 6, 6, 6, ... (ลำดับที่ 2) ${\displaystyle \ell }$${\displaystyle s_{n}=s_{n-\ell }}$${\displaystyle n\geq d}$${\displaystyle d}$

ลำดับที่กำหนดโดยพหุนามเป็นลำดับเวียนเกิดคงที่ ลำดับดังกล่าวเป็นไปตามความสัมพันธ์เวียนเกิดอันดับ(โดยที่คือดีกรีของพหุนาม) โดยมีสัมประสิทธิ์ที่กำหนดโดยองค์ประกอบที่สอดคล้องกันของ การแปลง ทวินาม^{[ 7 ] [ 8 ]}สมการแรกๆ ดังกล่าวคือ ${\displaystyle s_{n}=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{d}n^{d}}$${\displaystyle d+1}$${\displaystyle d}$

${\displaystyle s_{n}=1\cdot s_{n-1}}$สำหรับพหุนามดีกรี 0 (นั่นคือ ค่าคงที่)

${\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}}$สำหรับพหุนามดีกรี 1 หรือต่ำกว่า

${\displaystyle s_{n}=3\cdot s_{n-1}-3\cdot s_{n-2}+1\cdot s_{n-3}}$สำหรับพหุนามดีกรี 2 หรือต่ำกว่า และ

${\displaystyle s_{n}=4\cdot s_{n-1}-6\cdot s_{n-2}+4\cdot s_{n-3}-1\cdot s_{n-4}}$สำหรับพหุนามดีกรี 3 หรือต่ำกว่า

ลำดับที่สอดคล้องกับสมการอันดับdยังสอดคล้องกับสมการอันดับสูงกว่าทั้งหมดด้วย เอกลักษณ์เหล่านี้สามารถพิสูจน์ได้หลายวิธี รวมถึงผ่านทฤษฎีความแตกต่างจำกัด^{[ 9 ]} ลำดับใดๆ ของค่าจำนวนเต็ม จำนวนจริง หรือจำนวนเชิงซ้อนสามารถใช้เป็นเงื่อนไขเริ่มต้นสำหรับลำดับเวียนเกิดคงที่อันดับ d ได้หากเงื่อนไขเริ่มต้นอยู่บนพหุนามดีกรี d หรือน้อยกว่า ลำดับเวียนเกิดคงที่ยังสอดคล้องกับสมการอันดับต่ำกว่าด้วย ${\displaystyle d+1}$${\displaystyle d+1}$${\displaystyle d-1}$

ให้เป็นภาษาปกติและให้เป็นจำนวนคำที่มีความยาวในแล้วเป็นแบบเรียกซ้ำคงที่^{[ 10 ]}ตัวอย่างเช่นสำหรับภาษาของสตริงไบนารีทั้งหมดสำหรับภาษาของสตริงเอกภาคทั้งหมด และสำหรับภาษาของสตริงไบนารีทั้งหมดที่ไม่มีเลขหนึ่งสองตัวติดกัน โดยทั่วไปแล้ว ฟังก์ชันใดๆ ที่ยอมรับโดยออโตมาตาแบบถ่วงน้ำหนักเหนือตัวอักษรเอกภาคเหนือเซมิริง (ซึ่งจริงๆ แล้วเป็นริงและแม้แต่ฟิลด์ ) เป็นแบบเรียกซ้ำคงที่ ${\displaystyle L}$${\displaystyle s_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=2^{n}}$${\displaystyle s_{n}=1}$${\displaystyle s_{n}=F_{n+2}}$${\displaystyle \Sigma =\{a\}}$${\displaystyle (\mathbb {R} ,+,\times )}$

ลำดับของจำนวน JacobsthalจำนวนPadovanจำนวนPellและจำนวน Perrin ^{[ 2 ]}เป็นแบบเรียกซ้ำคงที่

ลำดับแฟกทอเรียลไม่ใช่ฟังก์ชันเวียนเกิดคงที่ โดยทั่วไปแล้ว ฟังก์ชันเวียนเกิดคงที่ทุกฟังก์ชันจะมีขอบเขตเชิงอะซิมโทติกโดยฟังก์ชันเลขชี้กำลัง (ดู#การกำหนดลักษณะในรูปแบบปิด ) และลำดับแฟกทอเรียลจะเติบโตเร็วกว่านี้ ${\displaystyle 1,1,2,6,24,120,720,\ldots }$

ลำดับคาตาลัน ไม่ใช่ลำดับเวียนเกิดคงที่ เนื่องจากฟังก์ชันก่อกำเนิดของจำนวนคาตาลันไม่ใช่ฟังก์ชันตรรกยะ (ดู#คำจำกัดความที่เทียบเท่ากัน ) ${\displaystyle 1,1,2,5,14,42,132,\ldots }$

${\displaystyle F_{n}={\begin{bmatrix}0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}.}$

นิยามของลำดับฟิโบนาชชีโดยใช้เมทริกซ์

ลำดับจะเป็นลำดับเวียนเกิดคงที่ที่มีอันดับน้อยกว่าหรือเท่ากับ ก็ต่อเมื่อสามารถเขียนได้ในรูป ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle d}$

${\displaystyle s_{n}=uA^{n}v}$

โดยที่เป็นเวกเตอร์เป็นเมทริกซ์และเป็นเวกเตอร์ โดยที่องค์ประกอบมาจากโดเมนเดียวกัน (จำนวนเต็ม จำนวนตรรกยะ จำนวนพีชคณิต จำนวนจริง หรือจำนวนเชิงซ้อน) เช่นเดียวกับลำดับเดิม โดยเฉพาะอย่างยิ่งสามารถนำมาเป็นค่าแรกของลำดับการแปลงเชิงเส้นที่คำนวณจากและเวกเตอร์^{[ 11 ]}${\displaystyle u}$${\displaystyle 1\times d}$${\displaystyle A}$${\displaystyle d\times d}$${\displaystyle v}$${\displaystyle d\times 1}$${\displaystyle v}$${\displaystyle d}$${\displaystyle A}$${\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}}$${\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}}$${\displaystyle u}$${\displaystyle [0,0,\ldots ,0,1]}$

ไม่เป็นเนื้อเดียวกัน	เอกพันธุ์
${\displaystyle s_{n}=1+s_{n-1}}$	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$
${\displaystyle s_{0}=0}$	${\displaystyle s_{0}=0;s_{1}=1}$

นิยามของลำดับจำนวนธรรมชาติ โดยใช้ความสัมพันธ์เวียนเกิดแบบไม่เอกพันธุ์ และความสัมพันธ์เวียนเกิดแบบเอกพันธุ์ที่เทียบเท่ากัน${\displaystyle s_{n}=n}$

ความสัมพันธ์เวียนเกิดเชิงเส้นที่ไม่เป็นเอกพันธุ์คือสมการที่มีรูปแบบดังนี้

${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d}+c}$

โดยที่เป็นค่าคงที่เพิ่มเติม ลำดับใดๆ ที่สอดคล้องกับความสัมพันธ์เวียนเกิดเชิงเส้นแบบไม่เอกพันธุ์ จะเป็นลำดับเวียนเกิดแบบค่าคงที่ เนื่องจากเมื่อลบสมการสำหรับ ออก จากสมการสำหรับ จะได้ความสัมพันธ์เวียนเกิดแบบเอกพันธุ์สำหรับซึ่งเราสามารถแก้หา เพื่อให้ได้ ${\displaystyle c}$${\displaystyle s_{n-1}}$${\displaystyle s_{n}}$${\displaystyle s_{n}-s_{n-1}}$${\displaystyle s_{n}}$

${\displaystyle {\begin{aligned}s_{n}=&(c_{1}+1)s_{n-1}\\&+(c_{2}-c_{1})s_{n-2}+\dots +(c_{d}-c_{d-1})s_{n-d}\\&-c_{d}s_{n-d-1}.\end{aligned}}}$

${\displaystyle \sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}.}$

นิยามของลำดับฟิโบนาชชีโดยใช้ฟังก์ชันก่อกำเนิด

ลำดับจะเป็นลำดับเวียนเกิดคงที่ก็ต่อเมื่อฟังก์ชันก่อกำเนิดของลำดับ นั้น

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}=s_{0}+s_{1}x^{1}+s_{2}x^{2}+s_{3}x^{3}+\cdots }$

เป็นฟังก์ชันตรรกยะโดยที่และเป็นพหุนาม และ[ ^{3 ] ยิ่ง} ไปกว่านั้น ลำดับของลำดับคือค่าต่ำสุดที่ทำให้มีรูปแบบดังกล่าวโดยที่และ^{[ 12 ]}${\displaystyle p(x)\,/\,q(x)}$${\displaystyle p}$${\displaystyle q}$${\displaystyle q(0)=1}$${\displaystyle d}$${\displaystyle {\text{deg }}q(x)\leq d}$${\displaystyle {\text{deg }}p(x)<d}$

ตัวส่วนคือพหุนามที่ได้จากพหุนามเสริมโดยการกลับลำดับของสัมประสิทธิ์และตัวเศษจะถูกกำหนดโดยค่าเริ่มต้นของลำดับ: ^{[ 13 ] [ 14 ]}

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}},}$

ที่ไหน

${\displaystyle b_{n}=s_{n}-c_{1}s_{n-1}-c_{2}s_{n-2}-\dots -c_{d}s_{n-d}.}$^{[ 15 ]}

จากที่กล่าวมาข้างต้น สรุปได้ว่าตัวส่วนจะต้องเป็นพหุนามที่ไม่หารลงตัวด้วย(และโดยเฉพาะอย่างยิ่งต้องไม่ใช่ศูนย์) ${\displaystyle q(x)}$${\displaystyle x}$

${\displaystyle \{(an+b)_{n=0}^{\infty }:a,b\in \mathbb {R} \}}$

ปริภูมิเวกเตอร์ 2 มิติของลำดับที่สร้างขึ้นโดยลำดับนั้น${\displaystyle s_{n}=n}$

ลำดับจะเป็นลำดับเวียนเกิดคงที่ก็ต่อเมื่อเซตของลำดับ ${\displaystyle (s_{n})_{n=0}^{\infty }}$

${\displaystyle \left\{(s_{n+r})_{n=0}^{\infty }:r\geq 0\right\}}$

บรรจุอยู่ในปริภูมิลำดับ ( ปริภูมิเวกเตอร์ของลำดับ) ซึ่ง มี มิติจำกัด นั่นคือ บรรจุอยู่ใน ปริภูมิย่อยมิติจำกัดของปิดภายใต้ตัวดำเนินการเลื่อนซ้าย^{[ 16 ] [ 17 ]}${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle \mathbb {C} ^{\mathbb {N} }}$

ลักษณะเฉพาะนี้เป็นเพราะความสัมพันธ์เวียนเกิดเชิงเส้นลำดับสามารถเข้าใจได้ว่าเป็นหลักฐานของการพึ่งพาเชิงเส้นระหว่างลำดับสำหรับ การขยาย ^ข้อโต้แย้งนี้แสดงให้เห็นว่าลำดับของลำดับเท่ากับมิติของปริภูมิของลำดับที่สร้างขึ้นโดยสำหรับทุก[ ^{18 ] [ 17 ]}${\displaystyle d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r=0,\ldots ,d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(1.618\ldots )^{n}-{\frac {1}{\sqrt {5}}}(-0.618\ldots )^{n}}$

การกำหนดลักษณะเฉพาะของลำดับฟิโบนาชชีในรูปแบบปิด ( สูตรของบิเนต์ )

ลำดับเวียนเกิดคงที่ยอมรับลักษณะ เฉพาะ ในรูปแบบปิดที่ไม่ซ้ำ กันโดยใช้ พหุนามเลขชี้กำลังดัง ต่อไปนี้ : ลำดับเวียนเกิดคงที่ทุกตัวสามารถเขียนได้ในรูปแบบ

${\displaystyle s_{n}=z_{n}+k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n},}$

สำหรับทุกคนที่ไหน ${\displaystyle n\geq 0}$

• เทอมนี้เป็นลำดับที่มีค่าเป็นศูนย์สำหรับทุกค่า(โดยที่คืออันดับของลำดับ)${\displaystyle z_{n}}$${\displaystyle n\geq d}$${\displaystyle d}$
• พจน์เหล่านี้เป็นพหุนามเชิงซ้อน และ${\displaystyle k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)}$
• เงื่อนไขเหล่านี้เป็นค่าคงที่เชิงซ้อนที่แตกต่างกัน^{[ 19 ] [ 3 ]}${\displaystyle r_{1},r_{2},\ldots ,r_{k}}$

ลักษณะเฉพาะนี้ถูกต้องแม่นยำ: ลำดับของจำนวนเชิงซ้อนทุกลำดับที่สามารถเขียนในรูปแบบข้างต้นได้นั้นเป็นแบบเรียกซ้ำคงที่^{[ 20 ]}

ตัวอย่างเช่น เลขฟิโบนาชชีเขียนในรูปแบบนี้โดยใช้สูตรของบิเนต์ : ^{[ 21 ]}${\displaystyle F_{n}}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\varphi ^{n}-{\frac {1}{\sqrt {5}}}\psi ^{n},}$

โดยที่คืออัตราส่วนทองคำและ. นี่คือรากของสมการ. ในกรณีนี้ , สำหรับทุก, ต่างก็เป็นพหุนามคงที่, และ. ${\displaystyle \varphi =(1+{\sqrt {5}})\,/\,2\approx 1.61803\ldots }$${\displaystyle \psi =-1\,/\,\varphi }$${\displaystyle x^{2}-x-1=0}$${\displaystyle e=2}$${\displaystyle z_{n}=0}$${\displaystyle n}$${\displaystyle k_{1}(n)=k_{2}(n)=1\,/\,{\sqrt {5}}}$${\displaystyle r_{1}=\varphi }$${\displaystyle r_{2}=\psi }$

เงื่อนไขนี้จำเป็นต้องใช้เฉพาะเมื่อ; ถ้าเป็นเช่นนั้น เงื่อนไขนี้จะแก้ไขข้อเท็จจริงที่ว่าค่าเริ่มต้นบางค่าอาจเป็นข้อยกเว้นจากความสัมพันธ์เวียนเกิดทั่วไป โดยเฉพาะอย่างยิ่งสำหรับทุกค่า ${\displaystyle z_{n}}$${\displaystyle c_{d}\neq 0}$${\displaystyle c_{d}=0}$${\displaystyle z_{n}=0}$${\displaystyle n\geq d}$

จำนวนเชิงซ้อนคือรากของพหุนามลักษณะเฉพาะของความสัมพันธ์เวียนเกิด: ${\displaystyle r_{1},\ldots ,r_{n}}$

${\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}$

ซึ่งมีสัมประสิทธิ์เหมือนกับสัมประสิทธิ์ของความสัมพันธ์เวียนเกิด^{[ 22 ]} เราเรียกสิ่งเหล่านี้ว่ารากของความสัมพันธ์เวียนเกิด ถ้าลำดับประกอบด้วยจำนวนเต็มหรือจำนวนตรรกยะ รากจะเป็นจำนวนพีชคณิตถ้าหากรากทั้งหมดแตกต่างกัน พหุนามทั้งหมดจะเป็นค่าคงที่ ซึ่งสามารถกำหนดได้จากค่าเริ่มต้นของลำดับ ถ้าหากรากของพหุนามลักษณะเฉพาะไม่แตกต่างกัน และเป็นรากที่มีความซ้ำซ้อนแล้วในสูตรจะมีดีกรีตัวอย่างเช่น ถ้าพหุนามลักษณะเฉพาะแยกตัวประกอบได้เป็น โดยมีราก rเดียวกันปรากฏสามครั้งพจน์ที่ th จะอยู่ในรูปแบบ^{[ 23 ] [ 24 ]}${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle d}$${\displaystyle r_{1},r_{2},\dots ,r_{d}}$${\displaystyle k_{i}(n)}$${\displaystyle r_{i}}$${\displaystyle m}$${\displaystyle k_{i}(n)}$${\displaystyle m-1}$${\displaystyle (x-r)^{3}}$${\displaystyle n}$${\displaystyle s_{n}=(a+bn+cn^{2})r^{n}.}$

ผลรวมของลำดับเวียนเกิดคงที่สองลำดับก็เป็นเวียนเกิดคงที่เช่นกัน^{[ 25 ] [ 26 ]}ตัวอย่างเช่น ผลรวมของและคือ( ) ซึ่งสอดคล้องกับเวียนเกิดเวียนเกิดใหม่สามารถหาได้โดยการบวกฟังก์ชันก่อกำเนิดสำหรับแต่ละลำดับ ${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=2^{n}+n}$${\displaystyle 1,3,6,11,20,\ldots }$${\displaystyle u_{n}=4u_{n-1}-5u_{n-2}+2u_{n-3}}$

ในทำนองเดียวกัน ผลคูณของลำดับแบบเรียกซ้ำคงที่สองลำดับจะเป็นแบบเรียกซ้ำคงที่^{[ 25 ]}ตัวอย่างเช่น ผลคูณของและคือ( ) ซึ่งสอดคล้องกับความสัมพันธ์เวียนเกิด ${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=n\cdot 2^{n}}$${\displaystyle 0,2,8,24,64,\ldots }$${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$

ลำดับการเลื่อนซ้ายและลำดับการเลื่อนขวา(โดยที่) เป็นลำดับเวียนเกิดคงที่ เนื่องจากมีความสัมพันธ์เวียนเกิดเดียวกัน ตัวอย่างเช่น เนื่องจากเป็นลำดับเวียนเกิดคงที่ ดังนั้น ก็เป็นลำดับเวียนเกิดคงที่เช่นกัน ${\displaystyle u_{n}=s_{n+1}}$${\displaystyle u_{n}=s_{n-1}}$${\displaystyle u_{0}=0}$${\displaystyle s_{n}=2^{n}}$${\displaystyle u_{n}=2^{n+1}}$

โดยทั่วไป ลำดับแบบเรียกซ้ำคงที่จะปิดภายใต้การดำเนินการต่อไปนี้ โดยที่แทนลำดับแบบเรียกซ้ำคงที่คือฟังก์ชันก่อกำเนิด และคือลำดับ ตามลำดับ^{[ 27 ]}${\displaystyle s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }}$${\displaystyle f(x),g(x)}$${\displaystyle d,e}$

การดำเนินการกับลำดับแบบเรียกซ้ำคงที่

การดำเนินการ	คำนิยาม	ความต้องการ	ฟังก์ชันสร้างเทียบเท่า	คำสั่ง
ผลรวมรายเทอม${\displaystyle s+t}$	${\displaystyle (s+t)_{n}=s_{n}+t_{n}}$	—	${\displaystyle f(x)+g(x)}$	${\displaystyle \leq d+e}$[ 25 ]
ผลิตภัณฑ์ตามระยะเวลา${\displaystyle s\cdot t}$	${\displaystyle (s\cdot t)_{n}=s_{n}\cdot t_{n}}$	—	${\displaystyle {\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(\zeta )}{\zeta }}g\left({\frac {x}{\zeta }}\right)\;\mathrm {d} \zeta }$[ 28 ] [ 29 ]	${\displaystyle \leq d\cdot e}$[ 11 ] [ 25 ]
ผลิตภัณฑ์คอชี${\displaystyle s*t}$	${\displaystyle (s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}}$	—	${\displaystyle f(x)g(x)}$	${\displaystyle \leq d+e}$[ 27 ]
เลื่อนไปทางซ้าย${\displaystyle Ls}$	${\displaystyle (Ls)_{n}=s_{n+1}}$	—	${\displaystyle {\frac {f(x)-s_{0}}{x}}}$	${\displaystyle \leq d}$[ 27 ]
เลื่อนไปทางขวา${\displaystyle Rs}$	${\displaystyle (Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}}$	—	${\displaystyle xf(x)}$	${\displaystyle \leq d+1}$[ 27 ]
การผกผันของโคชี${\displaystyle s^{(-1)}}$	${\displaystyle (s^{(-1)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}(-1)^{k}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=1}$	${\displaystyle {\frac {1}{f(x)}}}$	${\displaystyle \leq d+1}$[ 27 ]
คลีน สตาร์${\displaystyle s^{(*)}}$	${\displaystyle (s^{(*)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=0}$	${\displaystyle {\frac {1}{1-f(x)}}}$	${\displaystyle \leq d+1}$[ 27 ]

การปิดภายใต้การบวกและการคูณแบบเทอมต่อเทอมเป็นผลมาจากลักษณะเฉพาะของรูปแบบปิดในแง่ของพหุนามเลขชี้กำลัง การปิดภายใต้ผลคูณโคชีเป็นผลมาจากลักษณะเฉพาะของฟังก์ชันก่อกำเนิด^{[ 27 ]}ข้อกำหนดสำหรับตัวผกผันโคชีมีความจำเป็นสำหรับกรณีของลำดับจำนวนเต็ม แต่สามารถแทนที่ได้หากลำดับนั้นอยู่เหนือฟิลด์ ใดๆ (จำนวนตรรกยะ พีชคณิต จำนวนจริง หรือจำนวนเชิงซ้อน) ^{[ 27 ]}${\displaystyle s_{0}=1}$${\displaystyle s_{0}\neq 0}$

แม้ว่าจะตรงตามสูตรท้องถิ่นที่เรียบง่าย แต่ลำดับการเรียกซ้ำคงที่สามารถแสดงพฤติกรรมทั่วโลกที่ซับซ้อนได้ กำหนดให้ศูนย์ของลำดับการเรียกซ้ำคงที่เป็นจำนวนเต็มที่ไม่เป็นลบโดยที่ทฤษฎีบท Skolem–Mahler–Lech กล่าวว่าศูนย์ของลำดับจะซ้ำกันในที่สุด: มีค่าคงที่และที่ทำให้ สำหรับทุก ก็ต่อเมื่อผลลัพธ์นี้ใช้ได้กับลำดับการเรียกซ้ำคงที่เหนือจำนวนเชิงซ้อน หรือโดยทั่วไปแล้ว เหนือฟิลด์ ใดๆ ที่มีลักษณะเฉพาะเป็นศูนย์^{[ 30 ]}${\displaystyle n}$${\displaystyle s_{n}=0}$${\displaystyle M}$${\displaystyle N}$${\displaystyle n>M}$${\displaystyle s_{n}=0}$${\displaystyle s_{n+N}=0}$

รูปแบบของศูนย์ในลำดับแบบเรียกซ้ำคงที่ยังสามารถตรวจสอบได้จากมุมมองของทฤษฎีความสามารถในการคำนวณในการทำเช่นนั้น คำอธิบายของลำดับจะต้องได้รับการอธิบายแบบจำกัดซึ่งสามารถทำได้หากลำดับนั้นอยู่เหนือจำนวนเต็ม จำนวนตรรกยะ หรือจำนวนพีชคณิต^{[ 11 ]} เมื่อมีการเข้ารหัสลำดับดังกล่าวแล้วปัญหาต่อไปนี้สามารถศึกษาได้: ${\displaystyle s_{n}}$${\displaystyle s_{n}}$

ปัญหาการตัดสินใจที่สำคัญ

ปัญหา	คำอธิบาย	สถานะ[ 11 ] [ 31 ]
การมีอยู่ของศูนย์ ( ปัญหาสโกเลม )	เมื่อป้อนข้อมูลแล้ว ใช้สำหรับบางอย่างหรือไม่? ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$${\displaystyle n}$	เปิด
ศูนย์จำนวนอนันต์	เมื่อป้อนค่าเข้าไปจะมีจำนวนอนันต์หรือไม่? ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$${\displaystyle n}$	ตัดสินใจได้
ในที่สุดทุกอย่างก็จะเป็นศูนย์	เมื่อป้อนข้อมูลเข้าไป ค่าที่ได้จะมีขนาดใหญ่เพียงพอสำหรับทุกค่าหรือไม่? ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$${\displaystyle n}$	ตัดสินใจได้
ความคิดเชิงบวก	เมื่อป้อนข้อมูลแล้ว ใช้ได้กับทุกอย่าง หรือไม่ ? ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}>0}$${\displaystyle n}$	เปิด
ความคิดเชิงบวกในที่สุด	เมื่อป้อนข้อมูลเข้าไป ค่าที่ได้จะมีขนาดใหญ่เพียงพอสำหรับทุกค่าหรือไม่? ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}>0}$${\displaystyle n}$	เปิด

เนื่องจากกำลังสองของลำดับเวียนเกิดคงที่ยังคงเป็นเวียนเกิดคงที่ (ดูคุณสมบัติการปิด ) ปัญหาการมีอยู่ของศูนย์ในตารางข้างต้นจึงลดลงเหลือเพียงความเป็นบวก และปัญหาจำนวนศูนย์อนันต์ลดลงเหลือเพียงความเป็นบวกในที่สุด ปัญหาอื่นๆ ก็ลดลงเหลือเพียงปัญหาในตารางข้างต้นเช่นกัน ตัวอย่างเช่น การที่ เป็นจริงสำหรับบางค่าลดลงเหลือเพียงการมีอยู่ของศูนย์สำหรับลำดับตัวอย่างที่สอง สำหรับลำดับในจำนวนจริง ความเป็นบวก แบบอ่อน (เป็น จริง สำหรับทุกค่า?) ลดลงเหลือเพียงความเป็นบวกของลำดับ(เนื่องจากคำตอบต้องถูกปฏิเสธ นี่คือการลดรูปของทัวริง ) ${\displaystyle s_{n}^{2}}$${\displaystyle s_{n}=c}$${\displaystyle n}$${\displaystyle s_{n}-c}$${\displaystyle s_{n}\geq 0}$${\displaystyle n}$${\displaystyle -s_{n}}$

ทฤษฎีบท Skolem-Mahler-Lech จะให้คำตอบสำหรับคำถามเหล่านี้บางส่วน ยกเว้นว่าการพิสูจน์ของมันไม่ใช่แบบสร้างสรรค์มันระบุว่าสำหรับทุก ๆศูนย์จะซ้ำกัน อย่างไรก็ตาม ค่าของไม่เป็นที่รู้จักว่าสามารถคำนวณได้ ดังนั้นสิ่งนี้จึงไม่นำไปสู่การแก้ปัญหาการมีอยู่ของศูนย์^{[ 11 ]}ในทางกลับกัน รูปแบบที่แน่นอนซึ่งซ้ำกันหลังจากสามารถคำนวณได้^{[ 11 ] [ 32 ]}นี่คือเหตุผลที่ปัญหาศูนย์จำนวนอนันต์สามารถตัดสินได้: เพียงแค่พิจารณาว่ารูปแบบที่ซ้ำกันอย่างไม่สิ้นสุดนั้นว่างเปล่าหรือไม่ ${\displaystyle n>M}$${\displaystyle M}$${\displaystyle n>M}$

ผลลัพธ์ที่สามารถตัดสินได้นั้นทราบกันดีอยู่แล้วเมื่อลำดับของลำดับถูกจำกัดให้มีขนาดเล็ก ตัวอย่างเช่น ปัญหา Skolem สามารถตัดสินได้สำหรับลำดับพีชคณิตที่มีลำดับไม่เกิน 4 ^{[ 33 ] [ 34 ] [ 35 ]}นอกจากนี้ยังทราบกันดีว่าสามารถตัดสินได้สำหรับลำดับจำนวนเต็มที่ย้อนกลับได้จนถึงลำดับ 7 นั่นคือลำดับที่สามารถต่อย้อนกลับไปยังจำนวนเต็มได้^{[ 31 ]}

ผลลัพธ์ของการตัดสินใจได้นั้นเป็นที่รู้จักภายใต้สมมติฐานของข้อสันนิษฐานที่ยังไม่ได้รับการพิสูจน์บางประการในทฤษฎีจำนวนตัวอย่างเช่น การตัดสินใจได้เป็นที่รู้จักสำหรับลำดับตรรกยะที่มีอันดับไม่เกิน 5 ภายใต้ข้อสันนิษฐานที่เรียกว่าข้อสันนิษฐานของ Skolem หรือหลักการท้องถิ่น-ทั่วโลกแบบเอกซ์โพเนนเชียล การตัดสินใจได้ยังเป็นที่รู้จักสำหรับลำดับตรรกยะแบบง่ายทั้งหมด (ลำดับที่มี พหุนามลักษณะ เฉพาะแบบง่าย ) ภายใต้ข้อสันนิษฐานของ Skolem และข้อสันนิษฐานของ Schanuel แบบ p-adic ที่อ่อน^{[ 36 ]}

ให้และ เป็นรากเฉพาะของลำดับเวียนเกิดคงที่เรากล่าวว่าลำดับนั้นเป็นลำดับเสื่อม (degenerate) ถ้าอัตราส่วนเป็นรากของเอกภาพ (root of unity ) สำหรับทุกมักจะง่ายกว่าที่จะศึกษาลำดับที่ไม่เสื่อม (non-degenerate) และสามารถลดรูปไปสู่ลำดับนี้ได้โดยใช้ทฤษฎีบทต่อไปนี้: ถ้ามีอันดับและ อยู่ในฟิลด์จำนวนดีกรีเหนือแล้วจะมีค่าคงที่ อยู่${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle s}$${\displaystyle r_{i}/r_{j}}$${\displaystyle i\neq j}$${\displaystyle s}$${\displaystyle d}$${\displaystyle K}$${\displaystyle k}$${\displaystyle \mathbb {Q} }$${\displaystyle M(k,d)\leq {\begin{cases}\exp(2d(3\log d)^{1/2})&{\text{if }}k=1,\\2^{kd+1}&{\text{if }}k\geq 2\end{cases}}}$

โดยที่สำหรับบางลำดับย่อยจะมีค่าเป็นศูนย์โดยสมบูรณ์หรือไม่เสื่อมสภาพ^{[ 37 ]}${\displaystyle M\leq M(k,d)}$${\displaystyle s_{Mn+\ell }}$

ลำดับD-finite หรือลำดับโฮโลโนมิกเป็นการวางนัยทั่วไปตามธรรมชาติที่อนุญาตให้สัมประสิทธิ์ของการเกิดซ้ำเป็นฟังก์ชันพหุนามแทนที่จะเป็นค่าคงที่^{[ 38 ]}${\displaystyle n}$

ลำดับปกติ -regularเป็นไปตามความสัมพันธ์เวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์คงที่ แต่ความสัมพันธ์เวียนเกิดจะมีรูปแบบที่แตกต่างออกไป แทนที่จะเป็นการรวมเชิงเส้นของสำหรับจำนวนเต็มบางจำนวนที่ใกล้เคียงกับแต่ละพจน์ในลำดับปกติ -regular จะเป็นการรวมเชิงเส้นของสำหรับจำนวนเต็มบางจำนวนที่มี การ แสดงฐานใกล้เคียงกับของ[ 39 ^{]ลำดับเวียน}เกิดคงที่สามารถคิดได้ว่าเป็นลำดับปกติ -regular โดยที่การแสดงฐาน 1ของประกอบด้วยสำเนาของตัวเลข${\displaystyle k}$${\displaystyle s_{n}}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle s_{n}}$${\displaystyle k}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle k}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 1}$

• "คำแนะนำดัชนี OEIS "ดัชนี OEISรวบรวมตัวอย่างความสัมพันธ์เวียนเกิดเชิงเส้นหลายพันตัวอย่าง เรียงลำดับตามลำดับ (จำนวนพจน์) และลักษณะเฉพาะ (เวกเตอร์ของค่าสัมประสิทธิ์คงที่)