지수 재발

Question

허락하다 $f_0 = a, f_1 = b$. 밝히다$f_n = f_{n-1}$ 이상하게 $n$ 과 $$f_{n} = f_{n/2}+f_{n/2 - 1}$$이 반복을 어떻게 해결합니까? 일반적으로 나는 생성 함수를 사용하지만 분수가 나를 망치고 있습니다.

Answer 1

(나는 "$f_n=f_{n-1}$ 이상하게 $n$"포함 $n=1$, 그래서 $f_1=f_0$; 그렇지 않은 경우 유사한 방법이 적용되지만 더 짜증이납니다.)

밝히다 $F(x) = \sum_{n=0}^\infty f(n)x^n$ 과 $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. 이후$f_{n+1}=f_n$ 언제 $n$ 짝수, 우리는 $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. 반면에$f_{2m} = f_m + f_{m-1}$ (아마 $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*} 따라서 $$ F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2). $$ 교체 $x$ 으로 $x^2$ 준다 $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$, 의미하는 것은 $$ F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4). $$ 이 과정을 반복하면 $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}). $$ 한계를 $k\to\infty$ 준다 $$ 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, $$ 우리가 확인할 수있는 것은 주어진 반복을 만족시킵니다.

Answer 2

재발이 적용되는 경우 $n=1$, 그래서 $a=b$, 함수 생성에 전혀 의존하지 않고 반복을 해결하는 것은 매우 쉽습니다. 시퀀스의 처음 몇 항을 손으로 계산하면 다음과 같은 결과가 나타납니다.

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

매우 분명한 패턴이 있습니다. $f_{2n}=f_{2n+1}=(n+1)a$, 즉, $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. 이것은 유도에 의해 쉽게 증명됩니다.$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$ 심지어 $n$ 별도로 홀수.

만약 $a\ne b$그러나 가치는 $f_1$ 재발에 대한 예외입니다. 훨씬 더 복잡해집니다.