स्थिरांक-पुनरावर्ती अनुक्रम

फाइबोनैचि अनुक्रम स्थिर-पुनरावर्ती है: अनुक्रम का प्रत्येक तत्व पिछले दो का योग है।

निरंतर-पुनरावर्ती अनुक्रमों के कुछ उपवर्गों का हस्से आरेख, समावेशन द्वारा आदेशित

गणित और सैद्धांतिक कंप्यूटर विज्ञान में, एक निरंतर-पुनरावर्ती क्रम संख्याओं का एक क्रम होता है, जहां अनुक्रम में प्रत्येक संख्या अपने तत्काल पूर्ववर्तियों में से एक या अधिक के निश्चित रैखिक संयोजन के बराबर होती है। एक निरंतर-पुनरावर्ती अनुक्रम को रैखिक पुनरावृत्ति अनुक्रम, रैखिक-पुनरावर्ती अनुक्रम, रैखिक-आवर्तक अनुक्रम, सी-परिमित अनुक्रम, के रूप में भी जाना जाता है। या निरंतर गुणांक के साथ एक रैखिक पुनरावृत्ति का समाधान।

निरंतर-पुनरावर्ती अनुक्रम का सबसे प्रसिद्ध उदाहरण फाइबोनैचि संख्या है $0,1,1,2,3,5,8,13,\ldots$, जिसमें प्रत्येक संख्या पिछले दो का योग है। दो अनुक्रम की शक्ति $1,2,4,8,16,\ldots$ निरंतर-पुनरावर्ती भी है क्योंकि प्रत्येक संख्या पिछली संख्या के दोगुने का योग है। वर्ग संख्या अनुक्रम $0,1,4,9,16,25,\ldots$ निरंतर-पुनरावर्ती भी है। हालाँकि, सभी अनुक्रम निरंतर-पुनरावर्ती नहीं होते हैं; उदाहरण के लिए, कारख़ाने का अनुक्रम $1,1,2,6,24,120,\ldots$ निरंतर-पुनरावर्ती नहीं है। सभी अंकगणितीय प्रगति, सभी ज्यामितीय प्रगति और सभी बहुपद निरंतर-पुनरावर्ती हैं।

औपचारिक रूप से, संख्याओं का एक क्रम $s_{0},s_{1},s_{2},s_{3},\ldots$ निरंतर-पुनरावर्ती है यदि यह पुनरावृत्ति संबंध को संतुष्ट करता है

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

कहाँ $c_{i}$ स्थिर (गणित) हैं। उदाहरण के लिए, फाइबोनैचि अनुक्रम पुनरावृत्ति संबंध को संतुष्ट करता है $F_{n}=F_{n-1}+F_{n-2},$ कहाँ $F_{n}$ है $n$वें फाइबोनैचि संख्या।

साहचर्य और परिमित अंतर के सिद्धांत में निरंतर-पुनरावर्ती अनुक्रमों का अध्ययन किया जाता है। वे बीजगणितीय संख्या सिद्धांत में भी उत्पन्न होते हैं, एक बहुपद के बहुपद की जड़ के अनुक्रम के संबंध के कारण; सरल पुनरावर्तन (कंप्यूटर विज्ञान) के चलने के समय के रूप में कलन विधि के विश्लेषण में; और औपचारिक भाषा सिद्धांत में, जहां वे एक नियमित भाषा में दी गई लंबाई तक तार की गणना करते हैं। निरंतर-पुनरावर्ती अनुक्रम महत्वपूर्ण गणितीय परिचालनों के तहत बंद (गणित) हैं जैसे बिंदुवार | अवधि-वार जोड़, शब्द-वार गुणन, और कॉची उत्पाद।

स्कोलेम-महलर-लेच प्रमेय में कहा गया है कि निरंतर-पुनरावर्ती अनुक्रम के एक समारोह के शून्य में नियमित रूप से दोहराए जाने वाले (अंततः आवधिक) रूप होते हैं। दूसरी ओर, स्कोलेम समस्या, जो यह निर्धारित करने के लिए एक एल्गोरिद्म की मांग करती है कि क्या रैखिक पुनरावृत्ति में कम से कम एक शून्य है, गणित में अनसुलझी समस्याओं की एक प्रसिद्ध सूची है।

परिभाषा

एक निरंतर-पुनरावर्ती अनुक्रम पूर्णांकों, परिमेय संख्याओं, बीजगणितीय संख्याओं, वास्तविक संख्याओं या जटिल संख्याओं का कोई भी क्रम है $s_{0},s_{1},s_{2},s_{3},\ldots$ (के रूप में लिखा गया है $(s_{n})_{n=0}^{\infty }$ आशुलिपि के रूप में) प्रपत्र के एक सूत्र को संतुष्ट करना

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

सभी के लिए $n\geq d,$ कहाँ $c_{i}$ स्थिरांक हैं। (इस समीकरण को कोटि d के अचर गुणांकों के साथ एक रैखिक पुनरावृत्ति कहा जाता है।) निरंतर-पुनरावर्ती अनुक्रम का 'क्रम' सबसे छोटा होता है $d\geq 1$ ऐसा कि अनुक्रम उपरोक्त रूप के एक सूत्र को संतुष्ट करता है, या $d=0$ हर जगह-शून्य क्रम के लिए।

डी गुणांक $c_{1},c_{2},\dots ,c_{d}$ अनुक्रम (पूर्णांक, परिमेय संख्या, बीजगणितीय संख्या, वास्तविक संख्या, या जटिल संख्या) के समान डोमेन पर होने वाले गुणांक होने चाहिए। उदाहरण के लिए एक तर्कसंगत निरंतर-पुनरावर्ती अनुक्रम के लिए, $s_{i}$ और $c_{i}$ परिमेय संख्याएँ होनी चाहिए।

उपरोक्त परिभाषा अंततः-आवधिक अनुक्रम अनुक्रमों की अनुमति देती है जैसे $1,0,0,0,\ldots$ और $0,1,0,0,\ldots$. कुछ लेखकों को इसकी आवश्यकता होती है $c_{d}\neq 0$, जो ऐसे अनुक्रमों को बाहर करता है।

उदाहरण

Selected examples of integer constant-recursive sequences

Name	Order ($d$  )	First few values	Recurrence (for $n\geq d$ )	Generating function	OEIS
Zero sequence	0	0, 0, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {0}{1}}$	A000004
One sequence	1	1, 1, 1, 1, 1, 1, ...	$s_{n}=s_{n-1}$	${\frac {1}{1-x}}$	A000012
Characteristic function of $\{0\}$	1	1, 0, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {1}{1}}$	A000007
Powers of two	1	1, 2, 4, 8, 16, 32, ...	$s_{n}=2s_{n-1}$	${\frac {1}{1-2x}}$	A000079
Powers of −1	1	1, −1, 1, −1, 1, −1, ...	$s_{n}=-s_{n-1}$	${\frac {1}{1+x}}$	A033999
Characteristic function of $\{1\}$	2	0, 1, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {x}{1}}$	A063524
Decimal expansion of 1/6	2	1, 6, 6, 6, 6, 6, ...	$s_{n}=s_{n-1}$	${\frac {1+5x}{1-x}}$	A020793
Decimal expansion of 1/11	2	0, 9, 0, 9, 0, 9, ...	$s_{n}=s_{n-2}$	${\frac {9x}{1-x^{2}}}$	A010680
Nonnegative integers	2	0, 1, 2, 3, 4, 5, ...	$s_{n}=2s_{n-1}-s_{n-2}$	${\frac {x}{(1-x)^{2}}}$	A001477
Odd positive integers	2	1, 3, 5, 7, 9, 11, ...	$s_{n}=2s_{n-1}-s_{n-2}$	${\frac {1+x}{(1-x)^{2}}}$	A005408
Fibonacci numbers	2	0, 1, 1, 2, 3, 5, 8, 13, ...	$s_{n}=s_{n-1}+s_{n-2}$	${\frac {x}{1-x-x^{2}}}$	A000045
Lucas numbers	2	2, 1, 3, 4, 7, 11, 18, 29, ...	$s_{n}=s_{n-1}+s_{n-2}$	${\frac {2-x}{1-x-x^{2}}}$	A000032
Pell numbers	2	0, 1, 2, 5, 12, 29, 70, ...	$s_{n}=2s_{n-1}+s_{n-2}$	${\frac {x}{1-2x-x^{2}}}$	A000129
Powers of two interleaved with 0s	2	1, 0, 2, 0, 4, 0, 8, 0, ...	$s_{n}=2s_{n-2}$	${\frac {1}{1-2x^{2}}}$	A077957
Inverse of 6th cyclotomic polynomial	2	1, 1, 0, −1, −1, 0, 1, 1, ...	$s_{n}=s_{n-1}-s_{n-2}$	${\frac {1}{1-x+x^{2}}}$	A010892
Triangular numbers	3	0, 1, 3, 6, 10, 15, 21, ...	$s_{n}=3s_{n-1}-3s_{n-2}+s_{n-3}$	${\frac {x}{(1-x)^{3}}}$	A000217

फाइबोनैचि और लुकास अनुक्रम

फाइबोनैचि संख्याओं का क्रम 0, 1, 1, 2, 3, 5, 8, 13, ... क्रम 2 का निरंतर-पुनरावर्ती है क्योंकि यह पुनरावृत्ति को संतुष्ट करता है $F_{n}=F_{n-1}+F_{n-2}$ साथ $F_{0}=0,F_{1}=1$. उदाहरण के लिए, $F_{2}=F_{1}+F_{0}=1+0=1$ और $F_{6}=F_{5}+F_{4}=5+3=8$. लुकास संख्या का क्रम 2, 1, 3, 4, 7, 11, ... उसी पुनरावृत्ति को संतुष्ट करता है जो फिबोनाची अनुक्रम को संतुष्ट करता है लेकिन प्रारंभिक शर्तों के साथ $L_{0}=2$ और $L_{1}=1$. अधिक आम तौर पर, प्रत्येक लुकास अनुक्रम क्रम 2 का निरंतर-पुनरावर्ती होता है।

अंकगणितीय प्रगति

किसी के लिए $a$ और कोई भी $r\neq 0$, अंकगणितीय प्रगति $a,a+r,a+2r,\ldots$ क्रम 2 का निरंतर-पुनरावर्ती है, क्योंकि यह संतुष्ट करता है $s_{n}=2s_{n-1}-s_{n-2}$. इसे सामान्य करते हुए, नीचे निरंतर-पुनरावर्ती अनुक्रम#बहुपद अनुक्रम देखें।

ज्यामितीय प्रगति

किसी के लिए $a\neq 0$ और $r$, ज्यामितीय प्रगति $a,ar,ar^{2},\ldots$ क्रम 1 का निरंतर-पुनरावर्ती है, क्योंकि यह संतुष्ट करता है $s_{n}=rs_{n-1}$. इसमें शामिल है, उदाहरण के लिए, अनुक्रम 1, 2, 4, 8, 16, ... साथ ही परिमेय संख्या अनुक्रम $1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...$.

अंततः आवधिक अनुक्रम

एक अनुक्रम जो अंततः आवधिक अवधि के साथ आवधिक होता है $\ell$ निरंतर-पुनरावर्ती है, क्योंकि यह संतुष्ट करता है $s_{n}=s_{n-\ell }$ सभी के लिए $n\geq d$, जहां आदेश $d$ पहले दोहराए जाने वाले ब्लॉक सहित प्रारंभिक खंड की लंबाई है। ऐसे अनुक्रमों के उदाहरण 1, 0, 0, 0, ... (आदेश 1) और 1, 6, 6, 6, ... (आदेश 2) हैं।

बहुपद अनुक्रम

एक बहुपद द्वारा परिभाषित अनुक्रम $s_{n}=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{d}n^{d}$ निरंतर-पुनरावर्ती है। अनुक्रम आदेश की पुनरावृत्ति को संतुष्ट करता है $d+1$ (कहाँ $d$ बहुपद के बहुपद की डिग्री है), द्विपद परिवर्तन के संबंधित तत्व द्वारा दिए गए गुणांक के साथ। ऐसे पहले कुछ समीकरण हैं

$s_{n}=1\cdot s_{n-1}$ डिग्री 0 (अर्थात् स्थिर) बहुपद के लिए,

$s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}$ एक डिग्री 1 या उससे कम बहुपद के लिए,

$s_{n}=3\cdot s_{n-1}-3\cdot s_{n-2}+1\cdot s_{n-3}$ डिग्री 2 या उससे कम बहुपद के लिए, और

$s_{n}=4\cdot s_{n-1}-6\cdot s_{n-2}+4\cdot s_{n-3}-1\cdot s_{n-4}$ डिग्री 3 या उससे कम बहुपद के लिए।

ऑर्डर-डी समीकरण का पालन करने वाला अनुक्रम भी सभी उच्च क्रम समीकरणों का पालन करता है। ये सर्वसमिकाएं कई तरीकों से गणितीय प्रमाण हो सकती हैं, जिनमें परिमित भिन्नताओं के सिद्धांत के माध्यम से भी शामिल है। का कोई क्रम $d+1$ क्रम के निरंतर-पुनरावर्ती अनुक्रम के लिए पूर्णांक, वास्तविक, या जटिल मानों को प्रारंभिक स्थितियों के रूप में उपयोग किया जा सकता है $d+1$. यदि प्रारंभिक शर्तें डिग्री के बहुपद पर स्थित हैं $d-1$ या कम, तो निरंतर-पुनरावर्ती अनुक्रम भी निम्न क्रम समीकरण का पालन करता है।

एक नियमित भाषा में शब्दों की गणना

होने देना $L$ एक नियमित भाषा बनो, और रहने दो $s_{n}$ लंबाई के शब्दों की संख्या हो $n$ में $L$. तब $(s_{n})_{n=0}^{\infty }$ निरंतर-पुनरावर्ती है। उदाहरण के लिए, $s_{n}=2^{n}$ सभी बाइनरी स्ट्रिंग्स की भाषा के लिए, $s_{n}=1$ सभी यूनरी स्ट्रिंग्स की भाषा के लिए, और $s_{n}=F_{n+2}$ उन सभी बाइनरी स्ट्रिंग्स की भाषा के लिए जिनमें लगातार दो नहीं हैं। अधिक आम तौर पर, यूनरी वर्णमाला पर भारित automaton द्वारा स्वीकृत कोई भी फ़ंक्शन $\Sigma =\{a\}$ मोटी हो जाओ के ऊपर $(\mathbb {R} ,+,\times )$ (जो वास्तव में एक वलय (गणित) है, और यहाँ तक कि एक क्षेत्र (गणित)) निरंतर-पुनरावर्ती है।

अन्य उदाहरण

जैकबस्टल नंबरों, पडोवन संख्या ों, पेल नंबरों और पेरिन संख्या ों का क्रम निरंतर-पुनरावर्ती हैं।

गैर-उदाहरण

फैक्टोरियल अनुक्रम $1,1,2,6,24,120,720,\ldots$ निरंतर-पुनरावर्ती नहीं है। अधिक आम तौर पर, प्रत्येक निरंतर-पुनरावर्ती कार्य एक घातीय कार्य (देखें # बंद-रूप लक्षण वर्णन) द्वारा स्पर्शोन्मुख रूप से बाध्य होता है और तथ्यात्मक अनुक्रम इससे तेजी से बढ़ता है।

कैटलन अनुक्रम $1,1,2,5,14,42,132,\ldots$ निरंतर-पुनरावर्ती नहीं है। ऐसा इसलिए है क्योंकि कैटलन संख्या#पहला उपपत्ति एक परिमेय फलन नहीं है (देखें #समकक्ष परिभाषाएँ)।

समतुल्य परिभाषाएँ

मैट्रिसेस के संदर्भ में

Main article: Companion matrix

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

Definition of the Fibonacci sequence using matrices.

एक क्रम $(s_{n})_{n=0}^{\infty }$ क्रम का निरंतर-पुनरावर्ती है $\leq d$ अगर और केवल अगर इसे लिखा जा सकता है

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

कहाँ $u$ एक है $1\times d$ वेक्टर, $A$ एक है $d\times d$ मैट्रिक्स (गणित), और $v$ एक है $d\times 1$ सदिश, जहां तत्व मूल अनुक्रम के रूप में एक ही डोमेन (पूर्णांक, परिमेय संख्या, बीजगणितीय संख्या, वास्तविक संख्या या जटिल संख्या) से आते हैं। विशेष रूप से, $v$ प्रथम माना जा सकता है $d$ अनुक्रम के मान, $A$ रैखिक परिवर्तन जो गणना करता है $s_{n+1},s_{n+2},\ldots ,s_{n+d}$ से $s_{n},s_{n+1},\ldots ,s_{n+d-1}$, और $u$ वेक्टर $[0,0,\ldots ,0,1]$.

गैर-सजातीय रैखिक पुनरावृत्तियों के संदर्भ में

Main article: Linear recurrence with constant coefficients § Conversion to homogeneous form

गैर सजातीय	सजातीय
$s_{n}=1+s_{n-1}$	$s_{n}=2s_{n-1}-s_{n-2}$
$s_{0}=0$	$s_{0}=0;s_{1}=1$

Definition of the sequence of natural numbers $s_{n}=n$, using a non-homogeneous recurrence and the equivalent homogeneous version.

एक गैर-सजातीय रैखिक पुनरावृत्ति रूप का एक समीकरण है

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

कहाँ $c$ एक अतिरिक्त स्थिरांक है। गैर-सजातीय रैखिक पुनरावृत्ति को संतुष्ट करने वाला कोई भी क्रम निरंतर-पुनरावर्ती होता है। ऐसा इसलिए है क्योंकि के लिए समीकरण घटाना $s_{n-1}$ के लिए समीकरण से $s_{n}$ के लिए एक सजातीय पुनरावृत्ति देता है $s_{n}-s_{n-1}$, जिससे हम हल कर सकते हैं $s_{n}$ प्राप्त करने के लिए

${\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}}$

कार्यों को उत्पन्न करने के संदर्भ में

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

Definition of the Fibonacci sequence using a generating function.

एक अनुक्रम निरंतर-पुनरावर्ती होता है जब इसका निर्माण कार्य होता है

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

एक तर्कसंगत कार्य है ${\frac {p(x)}{q(x)}}$, कहाँ $p$ और $q$ बहुपद हैं और $q(0)\neq 0$. भाजक पारस्परिक बहुपद द्वारा सहायक बहुपद से प्राप्त बहुपद है, और अंश अनुक्रम के प्रारंभिक मूल्यों द्वारा निर्धारित किया जाता है।

रैखिक पुनरावृत्ति के संदर्भ में जनरेटिंग फ़ंक्शन की स्पष्ट व्युत्पत्ति है

$\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}}},$

कहाँ

$b_{n}=s_{n}-c_{1}s_{n-1}-c_{2}s_{n-2}-\dots -c_{d}s_{n-d}.$

ऊपर से यह इस प्रकार है कि यहाँ भाजक एक बहुपद होना चाहिए जो विभाज्य नहीं है $x$ (और विशेष रूप से अशून्य)।

अनुक्रम रिक्त स्थान के संदर्भ में

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

2-dimensional vector space of sequences generated by the sequence $s_{n}=n$.

एक क्रम $(s_{n})_{n=0}^{\infty }$ निरंतर-पुनरावर्ती है अगर और केवल अगर अनुक्रमों का सेट

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

अनुक्रम स्थान (अनुक्रमों का सदिश स्थल) में समाहित है जिसका आयाम (वेक्टर स्थान) परिमित है। वह है, $(s_{n})_{n=0}^{\infty }$ की एक परिमित आयामी रैखिक उपसमष्टि में समाहित है $\mathbb {C} ^{\mathbb {N} }$ शिफ्ट ऑपरेटर#सीक्वेंस|लेफ्ट-शिफ्ट ऑपरेटर के तहत क्लोजर (गणित)।

यह लक्षण वर्णन इसलिए है क्योंकि आदेश-$d$ रैखिक पुनरावृत्ति संबंध को अनुक्रमों के बीच रैखिक स्वतंत्रता#परिभाषा के रूप में समझा जा सकता है $(s_{n+r})_{n=0}^{\infty }$ के लिए $r=0,\ldots ,d$. इस तर्क के विस्तार से पता चलता है कि अनुक्रम का क्रम इसके द्वारा उत्पन्न अनुक्रम स्थान के आयाम के बराबर है $(s_{n+r})_{n=0}^{\infty }$ सभी के लिए $r$.

बंद-रूप लक्षण वर्णन

For a derivation of the closed form, see Linear recurrence with constant coefficients § General solution.

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

Closed-form characterization of the Fibonacci sequence (Binet's formula)

निरंतर-पुनरावर्ती अनुक्रम घातीय बहुपदों का उपयोग करके निम्नलिखित अद्वितीय बंद-रूप अभिव्यक्ति लक्षण वर्णन को स्वीकार करते हैं: प्रत्येक स्थिर-पुनरावर्ती अनुक्रम को रूप में लिखा जा सकता है

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

कहाँ

• $z_{n}$ एक क्रम है जो सभी के लिए शून्य है $n\geq d$ (अनुक्रम का क्रम);
• $k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)$ जटिल बहुपद हैं; और
• $r_{1},r_{2},\ldots ,r_{k}$ विशिष्ट जटिल स्थिरांक हैं।

यह विशेषता सटीक है: उपरोक्त रूप में लिखी जा सकने वाली जटिल संख्याओं का प्रत्येक क्रम स्थिर-पुनरावर्ती है।

उदाहरण के लिए, फाइबोनैचि संख्या $F_{n}$ फाइबोनैचि संख्या#बिनेट के सूत्र|बिनेट के सूत्र का उपयोग करके इस रूप में लिखा जाता है:

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

कहाँ $\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\ldots$ सुनहरा अनुपात है और $\psi ={\frac {-1}{\varphi }}$, समीकरण के दोनों मूल $x^{2}-x-1=0$. इस मामले में, $e=2$, $z_{n}=0$ सभी के लिए $n$, $k_{1}(n)=k_{2}(n)={\frac {1}{\sqrt {5}}}$ (निरंतर बहुपद), $r_{1}=\varphi$, और $r_{2}=\psi$. ध्यान दें कि हालांकि मूल अनुक्रम पूर्णांकों पर था, बंद रूप समाधान में वास्तविक या जटिल जड़ें शामिल हैं। सामान्य तौर पर, पूर्णांकों या परिमेय के अनुक्रमों के लिए, बंद सूत्र बीजगणितीय संख्याओं का उपयोग करेगा।

जटिल संख्याएँ $r_{1},\ldots ,r_{n}$ पुनरावृत्ति के चारित्रिक समीकरण (कैलकुलस) (या सहायक बहुपद) के मूल हैं:

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

जिनके गुणांक पुनरावृत्ति के समान हैं। अगर $d$ जड़ों $r_{1},r_{2},\dots ,r_{d}$ सभी भिन्न हैं, फिर बहुपद हैं $k_{i}(n)$ सभी स्थिरांक हैं, जिन्हें अनुक्रम के प्रारंभिक मानों से निर्धारित किया जा सकता है। यदि विशेषता बहुपद की जड़ें अलग नहीं हैं, और $r_{i}$ बहुलता (गणित) की जड़ है $m$, तब $k_{i}(n)$ सूत्र में डिग्री है $m-1$. उदाहरण के लिए, यदि विशेषता बहुपद कारकों के रूप में $(x-r)^{3}$, एक ही मूल r के साथ तीन बार आ रहा है, फिर the $n$वां पद रूप का है $s_{n}=(a+bn+cn^{2})r^{n}.$ शब्द $z_{n}$ केवल तभी आवश्यक है जब $c_{d}\neq 0$; अगर $c_{d}=0$ तो यह इस तथ्य के लिए सुधार करता है कि कुछ प्रारंभिक मान सामान्य पुनरावृत्ति के अपवाद हो सकते हैं। विशेष रूप से, $z_{n}=0$ सभी के लिए $n\geq d$, अनुक्रम का क्रम।

क्लोजर प्रॉपर्टीज

उदाहरण

दो स्थिर-पुनरावर्ती अनुक्रमों का योग भी निरंतर-पुनरावर्ती होता है। उदाहरण के लिए, का योग $s_{n}=2^{n}$ और $t_{n}=n$ है $u_{n}=2^{n}+n$ ($1,3,6,11,20,\ldots$), जो पुनरावृत्ति को संतुष्ट करता है $u_{n}=4u_{n-1}-5u_{n-2}+2u_{n-3}$. प्रत्येक अनुक्रम के लिए जनरेटिंग फ़ंक्शन जोड़कर नया पुनरावर्तन पाया जा सकता है।

इसी तरह, दो स्थिर-पुनरावर्ती अनुक्रमों का गुणनफल निरंतर-पुनरावर्ती होता है। उदाहरण के लिए, का उत्पाद $s_{n}=2^{n}$ और $t_{n}=n$ है $u_{n}=n\cdot 2^{n}$ ($0,2,8,24,64,\ldots$), जो पुनरावृत्ति को संतुष्ट करता है $u_{n}=4u_{n-1}-4u_{n-2}$.

लेफ्ट-शिफ्ट सीक्वेंस $u_{n}=s_{n+1}$ और राइट-शिफ्ट अनुक्रम $u_{n}=s_{n-1}$ (साथ $u_{0}=0$) निरंतर-पुनरावर्ती हैं क्योंकि वे समान पुनरावृत्ति संबंध को संतुष्ट करते हैं। उदाहरण के लिए, क्योंकि $s_{n}=2^{n}$ निरंतर-पुनरावर्ती है, इसलिए है $u_{n}=2^{n+1}$.

संचालन की सूची

सामान्य तौर पर, निरंतर-पुनरावर्ती अनुक्रम निम्नलिखित परिचालनों के तहत क्लोजर (गणित) होते हैं, जहां $s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }$ निरंतर-पुनरावर्ती दृश्यों को निरूपित करें, $f(x),g(x)$ उनके जनन कार्य हैं, और $d,e$ क्रमशः उनके आदेश हैं।

Operations on constant-recursive sequences

Operation	Definition	Requirement	Generating function equivalent	Order
Term-wise sum $s+t$	$(s+t)_{n}=s_{n}+t_{n}$	—	$f(x)+g(x)$	$\leq d+e$
Term-wise product $s\cdot t$	$(s\cdot t)_{n}=s_{n}\cdot t_{n}$	—	—	$\leq d\cdot e$
Cauchy product $s*t$	$(s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}$	—	$f(x)g(x)$	$\leq d+e$
Left shift $Ls$	$(Ls)_{n}=s_{n+1}$	—	${\frac {f(x)-s_{0}}{x}}$	$\leq d$
Right shift $Rs$	$(Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}$	—	$xf(x)$	$\leq d+1$
Cauchy inverse $s^{(-1)}$	$(s^{(-1)})_{n}=\sum _{i_{1}+\dots +i_{k}=n}(-1)^{k}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}$	$s_{0}=1$	${\frac {1}{f(x)}}$	$\leq \max(2d-1,2)$
Kleene star $s^{(*)}$	$(s^{(*)})_{n}=\sum _{i_{1}+\dots +i_{k}=n}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}$	$s_{0}=0$	${\frac {1}{1-f(x)}}$	$\leq \max(2d-1,2)$

घातीय बहुपदों के संदर्भ में शब्द-वार जोड़ और गुणा के तहत समापन बंद-रूप लक्षण वर्णन से होता है। कॉची उत्पाद के तहत बंद होने का परिणाम जनरेटिंग फ़ंक्शन लक्षण वर्णन से होता है। मांग $s_{0}=1$ पूर्णांक अनुक्रमों के मामले में कॉची व्युत्क्रम आवश्यक है, लेकिन इसके द्वारा प्रतिस्थापित किया जा सकता है $s_{0}\neq 0$ यदि अनुक्रम किसी भी क्षेत्र (गणित) (तर्कसंगत, बीजगणितीय, वास्तविक, या जटिल संख्या) पर है।

व्यवहार

Main articles: Skolem–Mahler–Lech theorem and Skolem problem

शून्य

एक साधारण स्थानीय सूत्र को संतुष्ट करने के बावजूद, एक निरंतर-पुनरावर्ती अनुक्रम जटिल वैश्विक व्यवहार प्रदर्शित कर सकता है। एक गैर-ऋणात्मक पूर्णांक होने के लिए निरंतर-पुनरावर्ती अनुक्रम के शून्य को परिभाषित करें $n$ ऐसा है कि $s_{n}=0$. स्कोलेम-महलर-लेच प्रमेय कहता है कि अनुक्रम के शून्य अंततः दोहरा रहे हैं: स्थिरांक मौजूद हैं $M$ और $N$ ऐसा कि सभी के लिए $n>M$, $s_{n}=0$ अगर और केवल अगर $s_{n+N}=0$. यह परिणाम जटिल संख्याओं पर निरंतर-पुनरावर्ती अनुक्रम के लिए, या अधिक सामान्यतः, विशेषता (बीजगणित) शून्य के किसी भी क्षेत्र (गणित) पर होता है।

निर्णय समस्याएं

कम्प्यूटेबिलिटी सिद्धांत के परिप्रेक्ष्य से निरंतर-पुनरावर्ती अनुक्रम में शून्य के पैटर्न की भी जांच की जा सकती है। ऐसा करने के लिए, अनुक्रम का विवरण $s_{n}$ एक स्ट्रिंग (कंप्यूटर विज्ञान) दिया जाना चाहिए; यह तब किया जा सकता है जब अनुक्रम पूर्णांकों या परिमेय संख्याओं, या बीजगणितीय संख्याओं पर भी हो। अनुक्रमों के लिए इस तरह के एक एन्कोडिंग को देखते हुए $s_{n}$, निम्नलिखित समस्याओं का अध्ययन किया जा सकता है:

Notable decision problems

Problem	Description	Status (2021)
Existence of a zero (Skolem problem)	On input $(s_{n})_{n=0}^{\infty }$, is $s_{n}=0$ for some $n$?	Open
Infinitely many zeros	On input $(s_{n})_{n=0}^{\infty }$, is $s_{n}=0$ for infinitely many $n$?	Decidable
Positivity	On input $(s_{n})_{n=0}^{\infty }$, is $s_{n}>0$ for all $n$?	Open
Eventual positivity	On input $(s_{n})_{n=0}^{\infty }$, is $s_{n}>0$ for all sufficiently large $n$?	Open

क्योंकि निरंतर-पुनरावर्ती अनुक्रम का वर्ग $s_{n}^{2}$ अभी भी निरंतर-पुनरावर्ती है (देखें # क्लोजर गुण), कमी (रिकर्सन सिद्धांत) सकारात्मकता के ऊपर तालिका में अस्तित्व-की-शून्य समस्या, और असीमित-अनेक-शून्य अंततः सकारात्मकता को कम कर देता है। उपरोक्त तालिका में अन्य समस्याएं भी कम हो जाती हैं: उदाहरण के लिए, क्या $s_{n}=c$ कुछ के लिए $n$ अनुक्रम के लिए शून्य के अस्तित्व को कम कर देता है $s_{n}-c$. दूसरे उदाहरण के रूप में, वास्तविक संख्याओं में अनुक्रमों के लिए, कमजोर सकारात्मकता (है $s_{n}\geq 0$ सभी के लिए $n$?) अनुक्रम की सकारात्मकता को कम कर देता है $-s_{n}$ (क्योंकि उत्तर को नकारा जाना चाहिए, यह ट्यूरिंग कमी है)।

स्कोलेम-महलर-लेच प्रमेय इनमें से कुछ प्रश्नों के उत्तर प्रदान करेगा, सिवाय इसके कि इसका प्रमाण रचनात्मक प्रमाण है। गैर-रचनात्मक। इसमें कहा गया है कि सभी के लिए $n>M$, शून्य दोहरा रहे हैं; हालाँकि, का मूल्य $M$ संगणनीय होने के लिए ज्ञात नहीं है, इसलिए यह अस्तित्व-की-शून्य समस्या का समाधान नहीं करता है।दूसरी ओर, सटीक पैटर्न जो बाद में दोहराता है $n>M$ गणना योग्य है। यही कारण है कि असीमित-शून्य-शून्य समस्या निर्णायक है: केवल यह निर्धारित करें कि असीमित-दोहराव वाला पैटर्न खाली है या नहीं।

निर्णायकता के परिणाम तब ज्ञात होते हैं जब किसी अनुक्रम का क्रम छोटा होने के लिए प्रतिबंधित होता है। उदाहरण के लिए, स्कोलेम समस्या 4 तक के क्रम के अनुक्रमों के लिए निर्णायक है।

सामान्यीकरण

• एक होलोनोमिक फ़ंक्शन एक प्राकृतिक सामान्यीकरण है जहां पुनरावृत्ति के गुणांकों को बहुपद कार्यों के रूप में अनुमति दी जाती है $n$ स्थिरांक के बजाय।
• एक के-नियमित अनुक्रम |$k$नियमित अनुक्रम स्थिर गुणांक के साथ एक रैखिक पुनरावृत्ति को संतुष्ट करता है, लेकिन पुनरावृत्ति एक अलग रूप लेती है। इसके बजाय $s_{n}$ का एक रैखिक संयोजन होना $s_{m}$ कुछ पूर्णांकों के लिए $m$ कि करीब हैं $n$, प्रत्येक शब्द $s_{n}$ में एक $k$-नियमित अनुक्रम का एक रैखिक संयोजन है $s_{m}$ कुछ पूर्णांकों के लिए $m$ जिसका मूलांक-$k$ प्रतिनिधित्व के करीब हैं $n$. निरंतर-पुनरावर्ती अनुक्रमों के बारे में सोचा जा सकता है $1$-नियमित अनुक्रम, जहां एकात्मक अंक प्रणाली|आधार-1 का प्रतिनिधित्व $n$ के होते हैं $n$ अंकों की प्रतियां $1$.

संदर्भ

• Kauers, Manuel; Paule, Peter (2010-12-01). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates (in English). Springer Vienna. p. 66. ISBN 978-3-7091-0444-6.

अग्रिम पठन

• Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Wesley. ISBN 978-0-201-55802-9.

बाहरी संबंध

• "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)