घातांक पुनरावृत्ति

Question

चलो $f_0 = a, f_1 = b$। परिभाषित करें$f_n = f_{n-1}$ विषम के लिए $n$ तथा $$f_{n} = f_{n/2}+f_{n/2 - 1}$$मैं इस पुनरावृत्ति को कैसे हल करूं? आम तौर पर मैं जनरेटिंग फ़ंक्शंस का उपयोग करता हूं लेकिन अंश मुझे खराब कर रहा है।

Answer 1

(मैं मान लूंगा कि "$f_n=f_{n-1}$ विषम के लिए $n$“शामिल हैं $n=1$, ताकि $f_1=f_0$; यदि ऐसा नहीं है, तो एक समान विधि लागू होगी लेकिन यह अधिक कष्टप्रद है।)

परिभाषित करें $F(x) = \sum_{n=0}^\infty f(n)x^n$ तथा $F_2(x) = \sum_{n\text{ even}} f(n)x^n$। जबसे$f_{n+1}=f_n$ कब अ $n$ यहां तक ​​कि, हमारे पास है $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$। दूसरी ओर, चूंकि$f_{2m} = f_m + f_{m-1}$ (संभवतः के लिए $m\ge1$), \begin{align*} F_2(x) = \sum_{m=0}^\infty f_{2m} x^{2m} &= f_0 + \sum_{m=1}^\infty (f_m + f_{m-1}) x^{2m} \\ &= f_0 + \bigg( {-}f_0 + \sum_{m=0}^\infty f_m x^{2m} \bigg) + \bigg( x^2 \sum_{m=1}^\infty f_{m-1} x^{2(m-1)} \bigg) \\ &= (1+x^2) F(x^2). \end{align*} इसलिए $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ फिर से बदलना $x$ द्वारा द्वारा $x^2$ देता है $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, जिसका अर्थ है कि $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ किसी भी के लिए इस प्रक्रिया को दोहराता है $k\ge1$, $$ F(x) = \prod_{j=0}^{k-1} (1+x^{2^j}) \prod_{j=1}^{k} (1+x^{2^j}) F(x^{2^k}). $$ सीमा के रूप में ले रहा है $k\to\infty$ देता है $$ F(x) = \prod_{j=0}^\infty (1+x^{2^j}) \prod_{j=1}^\infty (1+x^{2^j}) f_0 = \frac1{1-x} \frac1{1-x^2} f_0, $$ हम जाँच कर सकते हैं जो दिए गए पुनरावृत्ति को संतुष्ट करता है।

Answer 2

यदि पुनरावृत्ति कब लागू होती है $n=1$, ताकि $a=b$, यह सभी कार्यों को उत्पन्न करने के लिए सहारा के बिना पुनरावृत्ति को हल करने के लिए बहुत आसान है। अनुक्रम के पहले कुछ शब्दों को हाथ से गणना करने पर, हमें निम्नलिखित परिणाम मिलते हैं:

$$\begin{array}{rcc} n:&0&1&2&3&4&5\\\hline f_n:&a&a&2a&2a&3a&3a\\ &\\ n:&6&7&8&9&10&11\\\hline f_n:&4a&4a&5a&5a&6a&6a\\ \end{array}$$

बहुत स्पष्ट पैटर्न है: ऐसा प्रतीत होता है $f_{2n}=f_{2n+1}=(n+1)a$, यानी कि $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$। यह आसानी से प्रेरण पर सिद्ध होता है$n$:

$$\begin{align*} f_{2(n+1)}&=f_{n+1}+f_n\\ &=\left(\left\lfloor\frac{n+3}2\right\rfloor+\left\lfloor\frac{n+2}2\right\rfloor\right)a\\ &=(n+2)a\,, \end{align*}$$

जहां मामलों पर विचार करके अंतिम चरण किया जा सकता है $n$ सम और $n$ अलग से विषम।

अगर $a\ne b$, हालांकि, इतना है कि के मूल्य $f_1$ पुनरावृत्ति के लिए एक अपवाद है, यह एक अच्छा सौदा गड़बड़ हो जाता है।