インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

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

数学ガールの秘密ノート〜数列の広場〜
書籍『数学ガールの秘密ノート/数列の広場』

を読みました。オリジナル問題を作ってみたので挑戦してみてください*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 |\lambda_i| \neq |\lambda_j|
を満たすならば、恒等的に零ではない任意の解\{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:=|a_n/\lambda^n|とする。このとき、

\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 |l_{n}-l_N| \leq \sum_{i=N+1}^n|l_i-l_{i-1}| < \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

と評価できる。すなわち、l_n=o(n)が示された。 Q.E.D.

*1:この問題の作り方は高校時代の恩師に教えて頂きました。