Récurrence exponentielle

Question

Laisser $f_0 = a, f_1 = b$. Définir$f_n = f_{n-1}$ pour bizarre $n$ et $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Comment résoudre cette récurrence? Normalement, j'utiliserais des fonctions de génération, mais la fraction me dérange.

Answer 1

(Je suppose que "$f_n=f_{n-1}$ pour bizarre $n$"comprend $n=1$, de sorte que $f_1=f_0$; si ce n'est pas le cas, une méthode similaire s'appliquera mais cela devient plus ennuyeux.)

Définir $F(x) = \sum_{n=0}^\infty f(n)x^n$ et $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Puisque$f_{n+1}=f_n$ quand $n$ est égal, nous avons $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. D'autre part, depuis$f_{2m} = f_m + f_{m-1}$ (probablement pour $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*} Donc $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Remplacement $x$ par $x^2$ donne $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, ce qui signifie que $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Répéter ce processus donne, pour tout $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}). $$ Prenant la limite comme $k\to\infty$ donne $$ 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, $$ que nous pouvons vérifier satisfait les récurrences données.

Answer 2

Si la récurrence s'applique lorsque $n=1$, de sorte que $a=b$, il est très facile de résoudre la récurrence sans recourir du tout à la génération de fonctions. En calculant à la main les premiers termes de la séquence, nous obtenons les résultats suivants:

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

Il y a un schéma très évident: il semble que $f_{2n}=f_{2n+1}=(n+1)a$, c'est-à-dire que $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Ceci est facilement prouvé par induction sur$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*}$$

où la dernière étape peut être faite en considérant les cas $n$ même et $n$ impair séparément.

Si $a\ne b$, cependant, de sorte que la valeur de $f_1$ est une exception à la récurrence, cela devient beaucoup plus compliqué.