数列の漸近挙動に関するポアンカレの定理

数学ガールの秘密ノート〜数列の広場〜

を読みました。オリジナル問題を作ってみたので挑戦してみてください*1：

f:id:integers:20170403000812p:plain

定数係数線形漸化式

定数係数 $k+1$ 項間線形漸化式

$a_{n+k}=c_1a_{n+k-1}+\cdots +c_{k-1}a_n+c_k$

を考えましょう( $c_i \in \mathbb{C}$ )。これは特性方程式

$x^k=c_1x^{k-1}+\cdots +c_{k-1}x+c_k$

の根 $\lambda_1, \dots, \lambda_k$ (重複を込めて $k$ 個)の状況によって場合分けが発生しますが、例えば根が全て相異なるならば、一般項は

$\displaystyle a_n=c'_1\lambda_1^n+\cdots +c'_n\lambda_k^n$

と表すことが出来ます( $c'_1, \dots, c'_k \in \mathbb{C}$ )。

$\lambda_1 > \lambda_2 > \cdots > \lambda_n$ かつ、 $c'_1=\cdots =c'_{i-1}=0, \ c'_i \neq 0$ ならば、

$\displaystyle \lim_{n \to \infty}\frac{a_{n+1}}{a_n} = \lambda_i$

なる漸近挙動を示します。

Poincaréの定理

定数係数ではない漸化式

$a_{n+k}=c_1(n)a_{n+k-1}+\cdots +c_{k-1}(n)a_n+c_k(n)$

となると、もはや一般項を求めることは極めて難しくなります( $c_i(\cdot)\colon \mathbb{Z}_{\geq 0} \to \mathbb{C}$ )。

しかしながら、漸化式自体がある定数係数線形漸化式に漸近するならば、解の漸近挙動は分かります：

Poincaréの定理 漸化式

$a_{n+k}=c_1(n)a_{n+k-1}+\cdots +c_{k-1}(n)a_n+c_k(n)$

が
$\displaystyle \lim_{n \to \infty}c_i(n) = c_i \in \mathbb{C} \ (i=1, \dots, k)$ を満たし、特性方程式

$x^k=c_1x^{k-1}+\cdots +c_{k-1}x+c_k$

の(重複を許した)根 $\lambda_1, \dots, \lambda_k$ が

$\displaystyle \lambda_i \neq \lambda_j \Longrightarrow \left|\lambda_i\right| \neq \left|\lambda_j\right|$

を満たすならば、恒等的に零ではない任意の解 $\{a_n\}$ に対して、ある $i$ が存在して( $1 \leq i \leq k$ )

$\displaystyle \lim_{n \to \infty}\frac{a_{n+1}}{a_n} = \lambda_i$

が成り立つ。

証明はいつか書きたいと思いますが、とりあえず原論文をあげておきます：
H. Poincaré, Sur Les Equation Linéares aux Différentielles Ordinaires et aux Différence Finies, Amer. J. Math., 7 (1885), 203-258.

$n \to \infty$ における $a_n$ 自体の漸近挙動は次の補題から分かります：

補題 $\displaystyle \lim_{n \to \infty}\frac{a_{n+1}}{a_n}=\lambda \neq 0$ ならば、 $a_n=\pm \lambda^ne^{o(n)}$ .

証明. $b_n:=\left|a_n/\lambda^n\right|$ とする。このとき、

$\displaystyle \lim_{n \to \infty}\frac{b_{n+1}}{b_n} = \lim_{n \to \infty}\left| \frac{1}{\lambda}\frac{a_{n+1}}{a_n} \right| = 1$

なので、 $l_n:=\log b_n$ とおくと

$\displaystyle \lim_{n \to \infty}(l_{n+1}-l_n)=\lim_{n \to \infty}\log \frac{b_{n+1}}{b_n} = \log \left( \lim_{n \to \infty}\frac{b_{n+1}}{b_n}\right) = 1$ .

故に任意の $\varepsilon > 0$ に対して或る番号 $N$ が存在し、

$\displaystyle n \geq N \Longrightarrow \left|l_{n}-l_N\right| \leq \sum_{i=N+1}^n\left|l_i-l_{i-1}\right| < \frac{\varepsilon}{2}(n-N)$

が成り立つので(望遠鏡和に分けて三角不等式を用いた)、十分大きい $n$ に対して

$\displaystyle \left| \frac{l_n}{n} \right| < \frac{\varepsilon}{2} \left( 1-\frac{N}{n} \right) + \left| \frac{l_N}{n} \right| < \frac{\varepsilon}{2}+\frac{\varepsilon}{2} = \varepsilon$