数列の極限(2次)

方針

解答

⓪ 発想 — どう考え始めるか。 また $\frac{\infty }{\infty }$ だ。手順は前と同じ。分母の最高次で割る。

今度の最高次は $n^2$ である。

$$\frac{2n^2-1}{n^2+n}$$

次数が上がっても、やることは変わらない。

割ったあとは、$\frac{1}{n}\to 0$ と $\frac{1}{n^2}\to 0$ で、余計な項がすべて消える。

残るのは、最高次の係数どうしの比だけ。

$$\frac{2n^2}{n^2}=2$$

そう、答えは最初から見えている。 $n$ がとてつもなく大きいとき、$-1$ や $+n$ は $n^2$ に比べて無視できるほど小さい。

「$\frac{\infty }{\infty }$ の勝負は、最高次の項だけで決まる」 — 割り算は、その事実をきちんと示すための手続きなのだ。

分子・分母を $n^2$ で割る。

$$\frac{2n^2-1}{n^2+n}=\frac{2-\frac{1}{n^2}}{1+\frac{1}{n}}$$

$n\to \infty$ で $\frac{1}{n^2}\to 0$、$\frac{1}{n}\to 0$ なので

$$\underset{n\to \infty }{\lim }\frac{2n^2-1}{n^2+n}=\frac{2-0}{1+0}=2$$

まとめ:分母の最高次で割るのは $2$ 次でも同じ。$\frac{1}{n}$ や $\frac{1}{n^2}$ はすべて $0$ に。最高次の係数の比 $\frac{2}{1}$ が答えだ。

発展 — 一歩先へ。 「最高次だけが効く」という考え方は、数学を超えて広く使われている。

その名を、オーダー(次数)という。

コンピュータの世界では、こう書く。

$$2n^2-1=O(n^2)$$

「$n$ が大きいとき、本質的に $n^2$ のスケールで増える」という意味だ。 係数の $2$ も、定数の $-1$ も、まとめて無視する。

なぜ無視してよいのか。

$n$ が $2$ 倍になったとき、何倍になるかを見よう。

$$\frac{2(2n{)}^2}{2n^2}=4$$

係数 $2$ は約分で消える。 どんな係数でも、「$n$ が $2$ 倍で、時間は $4$ 倍」という性質は変わらない。

これがオーダーの考え方だ。細かい係数より、「どのスケールで増えるか」を見る。

実際の例で、その威力を確かめよう。

アルゴリズム $A$: $100n$ 回の計算($O(n)$) アルゴリズム $B$: $n^2$ 回の計算($O(n^2)$)

$n=10$ なら $A$ は $1000$ 回、$B$ は $100$ 回。$B$ のほうが $10$ 倍速い。

だが $n=1000$ なら $A$ は $10$ 万回、$B$ は $100$ 万回。$A$ が $10$ 倍速い。

$n=100$ 万なら $A$ は $1$ 億回、$B$ は $1$ 兆回。$A$ が $1$ 万倍速い。

係数 $100$ という巨大なハンデがあっても、$n$ が大きくなれば、次数の低いほうが必ず勝つ。

「大きな $n$ では、次数がすべてを決める。」

この原理があるから、ソートのアルゴリズムは $O(n^2)$ から $O(n\log n)$ への改良に、あれほど価値がある。

$n=100$ 万件のデータで

$$n^2=10^{12}\text{対}n{\log }_{2}n\approx 2\times 10^7$$

$5$ 万倍の差。 $1$ 日かかる処理が、$2$ 秒で終わる。

極限の考え方 — 「$n$ を大きくしたとき、何が支配的か」— は、こうして現代の技術を支えている。

細部を捨て、本質だけを見る。 それが極限の眼差しである。

別解

手を動かして、実際に数を入れてみる。

極限が"信じられない"ときは、数値実験がいちばんの薬だ。

$n$ を大きくしながら、値を計算する。

$$n=10:\frac{2(100)-1}{100+10}=\frac{199}{110}\approx 1.809$$

$$n=100:\frac{19999}{10100}\approx 1.980$$

$$n=1000:\frac{1999999}{1001000}\approx 1.998$$

$$n=10000:\approx 1.9998$$

$2$ に向かって、じりじりと近づいている。

しかも、常に $2$ より小さい。 下から $2$ に迫っている。

「本当に $2$ に近づくんだな」と、目で納得できる。

では、なぜ $2$ なのか。数の大きさを比べてみよう。

$n=1000$ のとき、それぞれの項の大きさは

$$2n^2=2,000,000,-1=-1$$ $$n^2=1,000,000,n=1,000$$

分子では、$2n^2$ が $200$ 万に対し、$-1$ はたった $1$。 ほとんど何もしていない。

分母でも、$n^2$ が $100$ 万に対し、$n$ は $1000$ — $0.1\%$ の影響しかない。

$n$ を大きくすればするほど、この差は開いていく。

だから、実質的にはこうだ。

$$\frac{2n^2-1}{n^2+n}\approx \frac{2n^2}{n^2}=2$$

「最高次の係数の比」が答えになる理由が、これで見える。

この直感を、一般化しておこう。

$$\underset{n\to \infty }{\lim }\frac{a{n}^2+\cdots }{b{n}^2+\cdots }=\frac{a}{b}$$

分子と分母の次数が同じなら、極限は最高次の係数の比。

さらに、次数が違う場合は?

• 分子の次数 $<$ 分母の次数 → $0$(分母が圧勝)
• 分子の次数 $>$ 分母の次数 → $\pm \infty$(分子が圧勝)
• 同じ次数 → 係数の比

この $3$ パターンを頭に入れておけば、$\frac{\infty }{\infty }$ の分数式は、一瞬で答えが分かる。

ただし、答えを"当てる"のと、"示す"のは別だ。 記述では、必ず最高次で割る計算を書く。直感は方向を示し、計算がそれを証明する。