Lặp lại theo cấp số nhân

Question

Để cho $f_0 = a, f_1 = b$. Định nghĩa$f_n = f_{n-1}$ cho lẻ $n$ và $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Làm cách nào để giải quyết việc tái diễn này? Thông thường tôi sẽ sử dụng các hàm tạo nhưng phân số này đang khiến tôi khó chịu.

Answer 1

(Tôi sẽ cho rằng "$f_n=f_{n-1}$ cho lẻ $n$" bao gồm $n=1$, vậy nên $f_1=f_0$; nếu không phải như vậy, một phương pháp tương tự sẽ được áp dụng nhưng nó sẽ gây khó chịu hơn.)

Định nghĩa $F(x) = \sum_{n=0}^\infty f(n)x^n$ và $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Từ$f_{n+1}=f_n$ khi nào $n$ thậm chí, chúng tôi có $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. Mặt khác, kể từ khi$f_{2m} = f_m + f_{m-1}$ (có lẽ cho $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*} vì thế $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Thay thế $x$ bởi $x^2$ cho $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, có nghĩa là $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Lặp lại quá trình này mang lại cho bất kỳ $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}). $$ Lấy giới hạn là $k\to\infty$ cho $$ 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, $$ mà chúng tôi có thể kiểm tra có đáp ứng các định kỳ đã cho hay không.

Answer 2

Nếu lặp lại áp dụng khi $n=1$, vậy nên $a=b$, rất dễ dàng để giải quyết việc lặp lại mà không cần dùng đến các hàm tạo. Tính bằng tay một số số hạng đầu tiên của dãy, ta được kết quả sau:

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

Có một mô hình rất rõ ràng: có vẻ như $f_{2n}=f_{2n+1}=(n+1)a$tức là $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Điều này dễ dàng được chứng minh bằng quy trình cảm ứng trên$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ơi mà bước cuối cùng có thể được thực hiện bằng cách xem xét các trường hợp $n$ thậm chí và $n$ lẻ riêng lẻ.

Nếu $a\ne b$Tuy nhiên, để giá trị của $f_1$ là một ngoại lệ cho sự lặp lại, nó trở nên lộn xộn hơn.