Perulangan eksponensial

Question

Membiarkan $f_0 = a, f_1 = b$. Menetapkan$f_n = f_{n-1}$ untuk aneh $n$ dan $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Bagaimana cara mengatasi kekambuhan ini? Biasanya saya akan menggunakan fungsi pembangkit tetapi fraksi itu mengacaukan saya.

Answer 1

(Saya akan berasumsi bahwa "$f_n=f_{n-1}$ untuk aneh $n$"termasuk $n=1$, maka $f_1=f_0$; jika bukan itu masalahnya, metode serupa akan diterapkan tetapi semakin menjengkelkan.)

Menetapkan $F(x) = \sum_{n=0}^\infty f(n)x^n$ dan $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Sejak$f_{n+1}=f_n$ kapan $n$ bahkan, kita punya $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. Di sisi lain, sejak$f_{2m} = f_m + f_{m-1}$ (mungkin untuk $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*} Karena itu $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Mengganti $x$ oleh $x^2$ memberi $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, yang artinya $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Mengulangi proses ini memberi, untuk apa pun $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}). $$ Mengambil batas sebagai $k\to\infty$ memberi $$ 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, $$ yang dapat kita periksa memenuhi pengulangan yang diberikan.

Answer 2

Jika kekambuhan berlaku kapan $n=1$, maka $a=b$, sangat mudah untuk mengatasi pengulangan tanpa harus membuat fungsi sama sekali. Menghitung dengan tangan beberapa suku pertama dari barisan, kita mendapatkan hasil sebagai berikut:

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

Ada pola yang sangat jelas: tampaknya begitu $f_{2n}=f_{2n+1}=(n+1)a$, yaitu, itu $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Ini mudah dibuktikan dengan induksi aktif$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*}$$

dimana langkah terakhir dapat dilakukan dengan mempertimbangkan kasus $n$ bahkan dan $n$ aneh secara terpisah.

Jika $a\ne b$, bagaimanapun, sehingga nilai $f_1$ merupakan pengecualian untuk pengulangan, ini akan jauh lebih berantakan.