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

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

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

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

निरंतर-पुनरावर्ती अनुक्रम का सबसे प्रसिद्ध उदाहरण फाइबोनैचि संख्या है $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$, जो ऐसे अनुक्रमों को बाह्य करता है।

उदाहरण

पूर्णांक स्थिर-पुनरावर्ती अनुक्रमों के चयनित उदाहरण

नाम	अनुक्रम ($d$  )	पहले कुछ मान	पुनरावृत्ति ($n\geq d$  के लिए)	जनक फलन	ओईआईएस
शून्य अनुक्रम	0	0, 0, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {0}{1}}$	A000004
एक क्रम	1	1, 1, 1, 1, 1, 1, ...	$s_{n}=s_{n-1}$	${\frac {1}{1-x}}$	A000012
$\{0\}$ की विशेषता फलन	1	1, 0, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {1}{1}}$	A000007
दो की शक्तियाँ	1	1, 2, 4, 8, 16, 32, ...	$s_{n}=2s_{n-1}$	${\frac {1}{1-2x}}$	A000079
−1 की शक्तियाँ	1	1, −1, 1, −1, 1, −1, ...	$s_{n}=-s_{n-1}$	${\frac {1}{1+x}}$	A033999
$\{1\}$ का विशेषता फलन	2	0, 1, 0, 0, 0, 0, ...	$s_{n}=0$	${\frac {x}{1}}$	A063524
1/6 का दशमलव विस्तार	2	1, 6, 6, 6, 6, 6, ...	$s_{n}=s_{n-1}$	${\frac {1+5x}{1-x}}$	A020793
1/11 का दशमलव विस्तार	2	0, 9, 0, 9, 0, 9, ...	$s_{n}=s_{n-2}$	${\frac {9x}{1-x^{2}}}$	A010680
अऋणात्मक पूर्णांक	2	0, 1, 2, 3, 4, 5, ...	$s_{n}=2s_{n-1}-s_{n-2}$	${\frac {x}{(1-x)^{2}}}$	A001477
विषम धनात्मक पूर्णांक	2	1, 3, 5, 7, 9, 11, ...	$s_{n}=2s_{n-1}-s_{n-2}$	${\frac {1+x}{(1-x)^{2}}}$	A005408
फाइबोनैचि संख्या	2	0, 1, 1, 2, 3, 5, 8, 13, ...	$s_{n}=s_{n-1}+s_{n-2}$	${\frac {x}{1-x-x^{2}}}$	A000045
स्नेकास संख्या	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
पेल संख्या	2	0, 1, 2, 5, 12, 29, 70, ...	$s_{n}=2s_{n-1}+s_{n-2}$	${\frac {x}{1-2x-x^{2}}}$	A000129
0s के साथ अंतःपत्रित दो की शक्तियाँ	2	1, 0, 2, 0, 4, 0, 8, 0, ...	$s_{n}=2s_{n-2}$	${\frac {1}{1-2x^{2}}}$	A077957
छठे साइक्लोटोमिक बहुपद का प्रतिलोम	2	1, 1, 0, −1, −1, 0, 1, 1, ...	$s_{n}=s_{n-1}-s_{n-2}$	${\frac {1}{1-x+x^{2}}}$	A010892
त्रिकोणीय संख्या	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: निरंतर गुणांक के साथ रैखिक पुनरावृत्ति §  सजातीय रूप में रूपांतरण

गैर सजातीय	सजातीय
$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$ क्रमशः उनके आदेश हैं।

निरंतर-पुनरावर्ती अनुक्रमों पर कार्य प्रणाली

कार्य प्रणाली	परिभाषा	मांग	जनक फलन उत्पन्न करना	अनुक्रम
पद के अनुसार योग $s+t$	$(s+t)_{n}=s_{n}+t_{n}$	—	$f(x)+g(x)$	$\leq d+e$
पद के अनुसार उत्पाद $s\cdot t$	$(s\cdot t)_{n}=s_{n}\cdot t_{n}$	—	—	$\leq d\cdot e$
कॉची उत्पाद $s*t$	$(s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}$	—	$f(x)g(x)$	$\leq d+e$
वाम-विस्थापन $Ls$	$(Ls)_{n}=s_{n+1}$	—	${\frac {f(x)-s_{0}}{x}}$	$\leq d$
दक्षिण विस्थापन $Rs$	$(Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}$	—	$xf(x)$	$\leq d+1$
कॉची प्रतिलोम $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)$
क्लेन स्टार $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: स्कोलेम-महलर-लेच प्रमेय and स्कोलम समस्या

शून्य

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

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

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

उल्लेखनीय निर्णय समस्याएं

समस्या	विवरण	स्थिति (2021)
शून्य का अस्तित्व (स्कोलेम समस्या)	निविष्टि $(s_{n})_{n=0}^{\infty }$ पर, कुछ $n$? के लिए $s_{n}=0$ है	संवृत
अपरिमित रूप से अनेक शून्य	निविष्टि $(s_{n})_{n=0}^{\infty }$पर, असीम रूप से बहुतों $n$? के लिए $s_{n}=0$ है	निर्धारणीय
धनात्मकता	निविष्टि $(s_{n})_{n=0}^{\infty }$ पर, सभी $n$? के लिए $s_{n}>0$ है	संवृत
अंततः धनात्मकता	निविष्टि $(s_{n})_{n=0}^{\infty }$ पर, सभी $n$? के लिए पर्याप्त रूप से बड़ा $s_{n}>0$ है	संवृत

क्योंकि निरंतर-पुनरावर्ती अनुक्रम का वर्ग $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)