Exponentielle Wiederholung

Question

Lassen $f_0 = a, f_1 = b$. Definieren$f_n = f_{n-1}$ für ungerade $n$ und $$f_{n} = f_{n/2}+f_{n/2 - 1}$$Wie löse ich diese Wiederholung? Normalerweise würde ich Generierungsfunktionen verwenden, aber der Bruchteil macht mich fertig.

Answer 1

(Ich werde davon ausgehen, dass "$f_n=f_{n-1}$ für ungerade $n$"beinhaltet $n=1$, so dass $f_1=f_0$;; Wenn dies nicht der Fall ist, wird eine ähnliche Methode angewendet, die jedoch ärgerlicher wird.)

Definieren $F(x) = \sum_{n=0}^\infty f(n)x^n$ und $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Schon seit$f_{n+1}=f_n$ wann $n$ ist gerade, wir haben $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. Auf der anderen Seite seit$f_{2m} = f_m + f_{m-1}$ (vermutlich für $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*} Deshalb $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ Ersetzen $x$ durch $x^2$ gibt $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, was bedeutet, dass $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ Das Wiederholen dieses Vorgangs ergibt für jeden $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}). $$ Das Limit nehmen als $k\to\infty$ gibt $$ 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, $$ was wir überprüfen können, erfüllt die gegebenen Wiederholungen.

Answer 2

Wenn die Wiederholung gilt, wenn $n=1$, so dass $a=b$Es ist sehr einfach, die Wiederholung zu lösen, ohne überhaupt Funktionen zu generieren. Wenn wir die ersten Terme der Sequenz von Hand berechnen, erhalten wir die folgenden Ergebnisse:

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

Es gibt ein sehr offensichtliches Muster: Es scheint, dass $f_{2n}=f_{2n+1}=(n+1)a$dh das $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. Dies lässt sich leicht durch Induktion am beweisen$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*}$$

wo der letzte Schritt unter Berücksichtigung der Fälle durchgeführt werden kann $n$ gerade und $n$ ungerade separat.

Wenn $a\ne b$jedoch, so dass der Wert von $f_1$ ist eine Ausnahme von der Wiederholung, es wird viel chaotischer.