Ricorrenza esponenziale

Question

Permettere $f_0 = a, f_1 = b$. Definire$f_n = f_{n-1}$ per dispari $n$ e $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Come risolvo questa ricorrenza? Normalmente userei le funzioni di generazione, ma la frazione mi sta rovinando.

Answer 1

(Presumo che "$f_n=f_{n-1}$ per dispari $n$"include $n=1$, così che $f_1=f_0$; in caso contrario, verrà applicato un metodo simile ma diventa più fastidioso.)

Definire $F(x) = \sum_{n=0}^\infty f(n)x^n$ e $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Da$f_{n+1}=f_n$ quando $n$ è pari, abbiamo $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. D'altra parte, da allora$f_{2m} = f_m + f_{m-1}$ (presumibilmente per $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*} Perciò $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Sostituzione $x$ di $x^2$ dà $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, che significa che $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Ripetere questo processo dà, per qualsiasi $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}). $$ Prendendo il limite come $k\to\infty$ dà $$ 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, $$ che possiamo controllare soddisfa le ricorrenze date.

Answer 2

Se la ricorrenza si applica quando $n=1$, così che $a=b$, è molto facile risolvere la ricorrenza senza ricorrere affatto alla generazione di funzioni. Calcolando a mano i primi termini della sequenza, otteniamo i seguenti risultati:

$$\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'è uno schema molto evidente: sembra quello $f_{2n}=f_{2n+1}=(n+1)a$, cioè quello $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Questo è facilmente dimostrato per induzione$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*}$$

dove il passaggio finale può essere eseguito considerando i casi $n$ anche e $n$ dispari separatamente.

Se $a\ne b$, tuttavia, in modo che il valore di $f_1$ è un'eccezione alla ricorrenza, diventa molto più complicato.