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

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

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

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

स्थिर-पुनरावर्ती अनुक्रम का सबसे प्रसिद्ध उदाहरण फाइबोनैचि संख्या $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$ प्रत्येक स्थान पर शून्य अनुक्रम के लिए एक सूत्र को संतुष्ट करता है।

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

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

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

अन्य उदाहरण

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

गैर-उदाहरण

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

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

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

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

Main article: अभिसार आव्यूह

$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)