Üstel yineleme

Question

İzin Vermek $f_0 = a, f_1 = b$. Tanımlamak$f_n = f_{n-1}$ garip için $n$ ve $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Bu yinelemeyi nasıl çözerim? Normalde oluşturma işlevlerini kullanırdım ama kesir beni alt üst ediyor.

Answer 1

(Bunu varsayacağım "$f_n=f_{n-1}$ garip için $n$" içerir $n=1$, Böylece $f_1=f_0$; eğer durum bu değilse, benzer bir yöntem uygulanacaktır ancak daha can sıkıcı hale gelir.)

Tanımlamak $F(x) = \sum_{n=0}^\infty f(n)x^n$ ve $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Dan beri$f_{n+1}=f_n$ ne zaman $n$ eşit mi, bizde $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. Öte yandan,$f_{2m} = f_m + f_{m-1}$ (muhtemelen için $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*} Bu nedenle $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Değiştiriliyor $x$ tarafından $x^2$ verir $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$bu şu anlama geliyor $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Bu süreci tekrarlamak, herhangi biri için verir $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}). $$ Limiti olarak almak $k\to\infty$ verir $$ 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, $$ Kontrol edebileceğimiz, verilen yinelemeleri tatmin ediyor.

Answer 2

Yineleme ne zaman geçerliyse $n=1$, Böylece $a=b$, fonksiyon oluşturmaya hiç başvurmadan yinelemeyi çözmek çok kolaydır. Dizinin ilk birkaç terimini elle hesaplayarak aşağıdaki sonuçları elde ederiz:

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

Çok açık bir model var: öyle görünüyor ki $f_{2n}=f_{2n+1}=(n+1)a$yani $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Bu, indüksiyonla kolayca kanıtlanır$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*}$$

davalar dikkate alınarak son adım nerede yapılabilir $n$ hatta ve $n$ ayrı ayrı garip.

Eğer $a\ne b$ancak, böylece değeri $f_1$ yinelemenin bir istisnasıdır, daha da karmaşıklaşır.