ในทางคณิตศาสตร์สมการ P-recursiveคือสมการเชิงเส้นของลำดับโดยที่ลำดับสัมประสิทธิ์สามารถแทนด้วยพหุนามได้ สม การ P-recursive เป็นสมการเวียนเกิด เชิงเส้น (หรือความสัมพันธ์เวียนเกิดเชิงเส้น หรือสมการผลต่างเชิงเส้น) ที่มีสัมประสิทธิ์เป็นพหุนาม สมการเหล่านี้มีบทบาทสำคัญในสาขาต่างๆ ของคณิตศาสตร์ โดยเฉพาะอย่างยิ่งในคณิตศาสตร์เชิงการจัดเรียง ลำดับที่เป็นคำตอบของสมการเหล่านี้เรียกว่าลำดับโฮโลโนมิก ลำดับ P-recursive หรือลำดับ D-finite

ตั้งแต่ปลายทศวรรษ 1980 เป็นต้นมา มีการพัฒนาอัลกอริทึมชุดแรกเพื่อหาคำตอบสำหรับสมการเหล่านี้ เซอร์เกย์ เอ. อับราโมฟ, มาร์โก เปตคอฟเช็กและมาร์ค ฟาน โฮเอจ ได้อธิบายอัลกอริทึมเพื่อหาคำตอบในรูปแบบพหุนาม ตรรกยะ ไฮเปอร์จีโอเมตริก และดาล็องแบร์

ให้เป็นฟิลด์ที่มีลักษณะเฉพาะเป็นศูนย์ (เช่น) , พหุนามสำหรับ, ลำดับ และลำดับที่ไม่ทราบค่า สมการเรียกว่า สมการเวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์เป็นพหุนาม (สมการเวียนเกิดทั้งหมดในบทความนี้มีรูปแบบนี้) ถ้าและไม่เป็นศูนย์ทั้งคู่ แล้วเรียกว่า อันดับของสมการ ถ้าเป็นศูนย์ สมการนั้นเรียกว่า สมการเอกพันธุ์ มิฉะนั้นจะเรียกว่า สมการอเอกพันธุ์ ${\textstyle \mathbb {K} }$${\textstyle \mathbb {K} =\mathbb {Q} }$${\textstyle p_{k}(n)\in \mathbb {K} [n]}$${\textstyle k=0,\dots ,r}$${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$$${\displaystyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$$${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle r}$${\textstyle f}$

สามารถเขียนได้อีกแบบหนึ่งว่า โดยที่เป็นตัวดำเนินการเวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์เป็นพหุนาม และเป็นตัวดำเนินการเลื่อน นั่นคือ ${\textstyle Ly=f}$${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$${\textstyle N}$${\textstyle N\,y(n)=y(n+1)}$

ให้หรือเทียบเท่ากับเป็นสมการเวียนเกิดที่มีสัมประสิทธิ์พหุนาม มีอัลกอริทึมหลายตัวที่คำนวณหาคำตอบของสมการนี้ อัลกอริทึมเหล่านี้สามารถคำนวณหาคำตอบที่เป็นพหุนาม ตรรกยะ ไฮเปอร์จีโอเมตริก และดาล็องแบร์ได้ คำตอบของสมการเอกพันธุ์จะกำหนดโดยเคอร์เนลของตัวดำเนินการเวียนเกิดเชิงเส้น: . ในฐานะที่เป็นปริภูมิย่อยของปริภูมิของลำดับ เคอร์เนลนี้มีฐาน . ^{[ 1 ]}ให้เป็นฐานของแล้วผลรวมอย่างเป็นทางการสำหรับค่าคงที่ใดๆเรียกว่าคำตอบทั่วไปของปัญหาเอกพันธุ์ถ้าเป็นคำตอบเฉพาะของ นั่น คือแล้วก็เป็นคำตอบของปัญหาอเอกพันธุ์ด้วย และเรียกว่าคำตอบทั่วไปของปัญหาอเอกพันธุ์ ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$${\textstyle Ly=f}$${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$${\textstyle \ker L}$${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$${\textstyle Ly=0}$${\textstyle {\tilde {y}}}$${\textstyle Ly=f}$${\textstyle L{\tilde {y}}=f}$${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$

ในช่วงปลายทศวรรษ 1980 Sergei A. Abramov ได้อธิบายอัลกอริทึมที่ค้นหาคำตอบพหุนามทั่วไปของสมการเวียนเกิด กล่าวคือมีด้านขวามือเป็นพหุนามเขา (และอีกไม่กี่ปีต่อมาMarko Petkovšek ) ได้ให้ขอบเขตดีกรีสำหรับคำตอบพหุนาม ด้วยวิธีนี้ ปัญหาจึงสามารถแก้ไขได้ง่ายๆ โดยพิจารณาระบบสมการเชิงเส้น [ ^{2 ] [ 3 ] [ 4 ] ใน}ปี 1995 Abramov, Bronstein และ Petkovšek แสดงให้เห็นว่ากรณีพหุนามสามารถแก้ไขได้อย่างมีประสิทธิภาพมากขึ้นโดยพิจารณา คำตอบอนุกรม กำลังของสมการเวียนเกิดในฐานกำลังเฉพาะ (กล่าวคือ ไม่ใช่ฐานปกติ) ^{[ 5 ]}${\textstyle y(n)\in \mathbb {K} [n]}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle (x^{n})_{n\in \mathbb {N} }}$

อัลกอริทึมอื่นๆ สำหรับการค้นหาคำตอบที่ครอบคลุมมากขึ้น (เช่น คำตอบเชิงตรรกะหรือเชิงเรขาคณิตสูง) ก็อาศัยอัลกอริทึมที่คำนวณคำตอบเชิงพหุนามเช่นกัน

ในปี พ.ศ. 2532 Sergei A. Abramov แสดงให้เห็นว่าสามารถหาคำตอบเชิงตรรกะ ทั่วไปได้ เช่น ที่มีด้านขวามือเป็นพหุนาม โดยใช้แนวคิดของตัวส่วนสากล ตัวส่วนสากลคือพหุนาม ที่ตัวส่วนของคำตอบเชิงตรรกะทุกตัวหาร ได้ลงตัวAbramov แสดงให้เห็นว่าสามารถคำนวณตัวส่วนสากลนี้ได้โดยใช้เพียงพหุนามสัมประสิทธิ์ตัวแรกและตัวสุดท้าย และ เท่านั้นการแทนที่ตัวส่วนสากลนี้ด้วยตัวส่วนที่ไม่ทราบค่าของคำตอบเชิงตรรกะทั้งหมดสามารถหาได้โดยการคำนวณคำตอบพหุนามทั้งหมดของสมการที่แปลงแล้ว^{[ 6 ]}${\textstyle y(n)\in \mathbb {K} (n)}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle u}$${\textstyle u}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\displaystyle y}$

ลำดับจะเรียกว่าลำดับไฮเปอร์จีโอเมตริกถ้าอัตราส่วนของพจน์ที่อยู่ติดกันสองพจน์เป็นฟังก์ชันตรรกยะใน นั่น คือซึ่งจะเป็นจริงก็ต่อเมื่อลำดับนั้นเป็นคำตอบของสมการเวียนเกิดอันดับหนึ่งที่มีสัมประสิทธิ์เป็นพหุนาม เซตของลำดับไฮเปอร์จีโอเมตริกไม่ใช่ปริภูมิย่อยของปริภูมิของลำดับ เนื่องจากไม่ปิดภายใต้การบวก ${\textstyle y(n)}$${\displaystyle n}$${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$

ในปี พ.ศ. 2535 Marko Petkovšekได้เสนออัลกอริทึมเพื่อหาคำตอบไฮเปอร์จีโอเมตริกทั่วไปของสมการเวียนเกิด โดยที่ด้านขวามือเป็นผลรวมของลำดับไฮเปอร์จีโอเมตริก อัลกอริทึมนี้ใช้รูปแบบปกติของฟังก์ชันตรรกยะของ Gosper-Petkovšek ด้วยการแสดงเฉพาะนี้ จึงเพียงพอที่จะพิจารณาคำตอบพหุนามของสมการที่แปลงแล้ว^{[ 3 ]}${\displaystyle f}$

แนวทางที่แตกต่างและมีประสิทธิภาพมากกว่านั้นมาจาก Mark van Hoeij โดยพิจารณารากของพหุนามสัมประสิทธิ์ตัวแรกและตัวสุดท้ายและ– เรียกว่าเอกลักษณ์ – เราสามารถสร้างวิธีแก้ปัญหาทีละขั้นตอนโดยใช้ข้อเท็จจริงที่ว่าลำดับไฮเปอร์จีโอเมตริกทุกตัวมีการแสดงในรูปแบบสำหรับบางค่าที่มีสำหรับและ โดยที่ แทนฟังก์ชันแกมมาและการปิดเชิงพีชคณิตของฟิลด์ดังนั้นจะต้องเป็นเอกลักษณ์ของสมการ (เช่น รากของหรือ) นอกจากนี้ยังสามารถคำนวณขอบเขตสำหรับเลขชี้กำลังได้สำหรับค่าคงที่ เป็นไปได้ที่จะสร้างสมมติฐานซึ่งให้ตัวเลือกสำหรับ สำหรับค่าเฉพาะเราสามารถสร้างสมมติฐานอีกครั้งเพื่อให้ได้ฟังก์ชันตรรกยะโดยใช้อัลกอริทึมของ Abramov เมื่อพิจารณาความเป็นไปได้ทั้งหมด จะได้วิธีแก้ปัญหาทั่วไปของสมการเวียนเกิด^{[ 7 ] [ 8 ]}${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle y(n)}$$${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$${\textstyle i\neq j}$${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$${\textstyle \Gamma (n)}$${\textstyle {\overline {\mathbb {K} }}}$${\textstyle \mathbb {K} }$${\textstyle \xi _{1},\dots ,\xi _{s}}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle e_{i}}$${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$${\textstyle z}$${\textstyle z}$${\textstyle r(n)}$

ลำดับเรียกว่าลำดับดาลัมแบร์เชียน ถ้าสำหรับลำดับไฮเปอร์จีโอเมตริกบางลำดับและหมายความว่าโดยที่แทนตัวดำเนินการผลต่างนั่นคือ กรณีนี้เกิดขึ้นก็ต่อเมื่อมีตัวดำเนินการเวียนเกิดเชิงเส้นอันดับแรกที่มีสัมประสิทธิ์ตรรกยะเช่นนั้น^{[ 4 ]}${\displaystyle y}$${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$${\textstyle h_{1},\dots ,h_{k}}$${\textstyle y=\sum x}$${\textstyle \Delta y=x}$${\textstyle \Delta }$${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$${\textstyle L_{1},\dots ,L_{k}}$${\textstyle L_{k}\cdots L_{1}y=0}$

ในปี 1994 Abramov และ Petkovšek ได้อธิบายอัลกอริทึมที่คำนวณคำตอบ d'Alembertian ทั่วไปของสมการเวียนเกิด อัลกอริทึมนี้คำนวณคำตอบไฮเปอร์จีโอเมตริกและลดลำดับของสมการเวียนเกิดแบบเวียนเกิด^{[ 9 ]}

จำนวนเมทริกซ์การเรียงสับเปลี่ยนแบบมีเครื่องหมายที่มีขนาดสามารถอธิบายได้ด้วยลำดับเมทริกซ์การเรียงสับเปลี่ยนแบบมีเครื่องหมายคือเมทริกซ์จัตุรัสที่มีสมาชิกที่ไม่เป็นศูนย์เพียงตัวเดียวในแต่ละแถวและในแต่ละคอลัมน์ สมาชิกที่ไม่เป็นศูนย์อาจเป็นลำดับนี้ถูกกำหนดโดยสมการเวียนเกิดเชิงเส้นที่มีสัมประสิทธิ์พหุนามและค่าเริ่มต้นการใช้อัลกอริทึมเพื่อหาคำตอบไฮเปอร์จีโอเมตริกจะทำให้สามารถหาคำตอบไฮเปอร์จีโอเมตริกทั่วไปสำหรับค่าคงที่บางค่าได้ นอกจากนี้ เมื่อพิจารณาค่าเริ่มต้น ลำดับนี้ยังอธิบายจำนวนเมทริกซ์การเรียงสับเปลี่ยนแบบมีเครื่องหมาย ด้วย ^{[ 10 ]}${\displaystyle n\times n}$${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$${\textstyle \pm 1}$$${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$${\textstyle y(0)=1,y(1)=2}$$${\displaystyle y(n)=c\,2^{n}n!}$$${\textstyle c}$${\textstyle y(n)=2^{n}n!}$

จำนวนการผกผัน ของเซตที่มีองค์ประกอบจะได้รับจากสมการเวียนเกิดตัวอย่างเช่น การใช้อัลกอริทึมของ Petkovšekจะเห็นได้ว่าไม่มีคำตอบที่เป็นพหุนาม ตรรกยะ หรือไฮเปอร์จีโอเมตริกสำหรับสมการเวียนเกิดนี้^{[ 4 ]}${\textstyle y(n)}$${\textstyle n}$$${\displaystyle y(n)=(n-1)\,y(n-2)+y(n-1).}$$

ฟังก์ชันเรียกว่าไฮเปอร์จีโอเมตริก ถ้าโดยที่แทนฟังก์ชันตรรกยะในและผลรวมไฮเปอร์จีโอเมตริกคือผลรวมจำกัดในรูปแบบโดยที่เป็นไฮ เปอร์จีโอเมตริก อัลกอริทึมเทเลสโคปิกแบบสร้างสรรค์ของ Zeilbergerสามารถแปลงผลรวมไฮเปอร์จีโอเมตริกดังกล่าวให้เป็นสมการเวียนเกิดที่มีสัมประสิทธิ์พหุนาม จากนั้นสามารถแก้สมการนี้เพื่อให้ได้ตัวอย่างเช่น การรวมเชิงเส้นของผลรวมไฮเปอร์จีโอเมตริก ซึ่งเรียกว่าผลรวมรูปแบบปิดของ^{[ 4 ]}${\textstyle F(n,k)}$${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$${\textstyle \mathbb {K} (n,k)}$${\textstyle n}$${\textstyle k}$${\textstyle f(n)=\sum _{k}F(n,k)}$${\textstyle F(n,k)}$${\textstyle f}$