COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

階差数列

階差数列

定義≪階差数列≫

 数列 $\{ a_n\}$ に対して, $a_{n+1}-a_n$ を一般項とする数列を $\{ a_n\}$ の階差数列(difference sequence)と呼ぶ.

定理≪階差数列と一般項≫

 数列 $\{ a_n\}$ の階差数列が $\{ d_n\}$ であるならば, $n \geqq 2$ のとき \[ a_n = a_1+\sum_{k = 1}^{n-1}d_k\] が成り立つ.

問題≪モーザーの円の分割問題≫

 円周上に $n$ 個の点 $\mathrm P_1,$ $\cdots,$ $\mathrm P_n$ をとり, それらの点どうしをすべて互いに弦で結んだとき, どの $2$ 本の弦も互いに平行でなく, どの $3$ 本の弦も円の内部において $1$ 点で交わらないとする. このとき, 円が分割されてできる領域の個数を $a_n$ とおく.
(1)
円周上にとる点の個数が $n+1$ の場合を考える. $1 \leqq k \leqq n$ なる整数 $k$ に対して, 円周上にとる点の個数が $n$ の場合から弦 $\mathrm P_k\mathrm P_{n+1}$ を引くと, 領域は $(k-1)(n-k)+1$ 個増えることを説明せよ.
(2)
$n$ を用いて $a_{n+1}-a_n$ を表せ.
(3)
$n$ を用いて $a_n$ を表せ.

解答例

(1)
点 $\mathrm P_k$ から点 $\mathrm P_{n+1}$ に向かって弦 $\mathrm P_k\mathrm P_{n+1}$ を引いていくと, 既存の弦と交わるたびに領域が $1$ 個ずつ増えて, 点 $\mathrm P_{n+1}$ に達したときに領域がさらに $1$ 個増える. 弦 $\mathrm P_k\mathrm P_{n+1}$ と交わる弦はその両側の点を結んだ $(k-1)(n-k)$ 本の弦 $\mathrm P_i\mathrm P_j$ $(1 \leqq i \leqq k-1,$ $k+1 \leqq j \leqq n+1)$ に限るから, 領域は全部で $(k-1)(n-k)+1$ 個増える.
(2)
円周上にとる点の個数が $n$ の場合から $n$ 本の弦 $\mathrm P_k\mathrm P_{n+1}$ $(1 \leqq k \leqq n)$ を引くときに増える領域の個数を考えると, (1) の結果から, \begin{align*} &a_{n+1}-a_n \\ &= \sum_{k = 1}^n\{ (k-1)(n-k)+1\} \\ &= \sum_{k = 1}^n\{ -k^2+(n+1)k+(1-n)\} \\ &= -\frac{1}{6}n(n+1)(2n+1)+\frac{1}{2}n(n+1)^2+(1-n)n \\ &= \frac{1}{6}n\{ -(n+1)(2n+1)+3(n+1)^2+6(1-n)\} \\ &= \frac{1}{6}n(n^2-3n+8) \end{align*} が得られる.
(3)
$n \geqq 2$ のとき, (2) の結果から, \begin{align*} a_n &= a_1+\sum_{k = 1}^{n-1}\frac{1}{6}k(k^2-3k+8) \\ &= 1+\frac{1}{6}\sum_{k = 1}^{n-1}(k^3-3k^2+8k) \\ &= 1+\frac{1}{6}\left\{\frac{1}{4}(n-1)^2n^2\right. \\ &\qquad \left.-3\cdot\frac{1}{6}(n-1)n(2n-1)+8\cdot\frac{1}{2}(n-1)n\right\} \\ &= 1+\frac{1}{24}(n-1)n\{ (n-1)n-2(2n-1)+16\} \\ &= 1+\frac{1}{24}(n-1)n(n^2-5n+18) \\ &= \frac{1}{24}(n^4-6n^3+23n^2-18n+24) \end{align*} が得られる. これは $n = 1$ のときも成り立つ. ゆえに, すべての正の整数 $n$ に対して $a_n = \dfrac{1}{24}(n^4-6n^3+23n^2-18n+24)$ が成り立つ.

背景

 本問は,「モーザーの円の分割問題」(Moser's circle problem)としてよく知られている. \[ a_1 = 1, \quad a_2 = 2, \quad a_3 = 4, \quad a_4 = 8, \quad a_5 = 16\] から $a_n = 2^{n-1}$ と推測してしまいそうだが, $a_6 = 31$ で $\{ a_n\}$ は等比数列でない. このことから, \[ \{ a_n\}:a_1,\ a_2,\ a_3,\ a_4,\ a_5,\ \cdots\] のように「$\cdots$」を使って数列を表すときには十分な注意を払うべきことがわかる.

問題≪シュタイナーの平面の分割問題≫

 どの $2$ 本も平行でなく, どの $3$ 本も $1$ 点で交わらないように, 平面上に $n$ 本の直線を引く. このとき, 円が分割されてできる領域の個数 $a_n$ を求めよ.

解答例

 $n$ 本の直線を引いた状態から新たに $1$ 本の直線を引いていくと, 既存の直線と交わるたびに領域が $1$ 個ずつ増え, 全部で $n+1$ 個の領域が増えるので, \[ a_{n+1}-a_n = n+1\] が成り立つ.
また, $a_1 = 2$ であるから, $n \geqq 2$ のとき \begin{align*} a_n &= a_1+\sum_{k = 1}^{n-1}(a_{k+1}-a_k) \\ &= 2+\sum_{k = 1}^{n-1}(k+1) \\ &= 2+\frac{(n-1)n}{2}+(n-1) \\ &= \frac{n^2+n+2}{2} \end{align*} が成り立つ. これは $n = 1$ のときも成り立つ.