COMPASS

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

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

群数列・その他

理論

群数列

定義≪群数列(Sequence of finite progressions)≫

 正の整数から成る狭義単調増加な数列 $f$ と数列 $\{ a_n\}$ が合成可能なとき, $f(0) = 0$ として, 正の整数 $m$ に対して有限数列 $\{ a_{f(m-1)+n}\}_{n = 1}^{f(m)-f(m-1)}$ を対応させる写像を, $\{ a_n\}$ を区切った群数列(sequence of finite progressions)と呼ぶ. 正の整数 $m$ に対応する有限数列 \[ a_{f(m-1)+1},\ \cdots,\ a_{f(m)}\] をその第 $m$ 群($m$-th progression)と呼ぶ. この群数列を \[ a_1,\ \cdots,\ a_{f(1)}|a_{f(1)+1},\ \cdots,\ a_{f(2)}|\cdots\] のように区切り線と共に群の項を列記して表すこともある. $\{ a_n\}$ の初項, (存在すれば)末項をそれぞれ群数列の初項, 末項と呼ぶ.

等差数列を区切った群数列

例≪等差数列を区切った群数列:群の項数が等比数列の場合≫

 第 $m$ 群の項数が $2^{m-1}$ となるように数列 $\{ n\}$ を区切った群数列 \[ 1|2,\ 3|4,\ 5,\ 6,\ 7|8,\ 9,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15|\cdots\] の第 $m$ 群の第 $n$ 項 $A_{m,n},$ 第 $m$ 群の和 $S_m$ を求める.
(1)
第 $m$ 群の末項までの項数を $f(m)$ とおくと, \[ f(m) = \sum\limits_{k = 1}^m2^{k-1} = \frac{1\cdot (2^m-1)}{2-1} = 2^m-1 \quad \cdots [\ast ].\] よって, $m > 1$ のとき, 第 $m$ 群の初項は, \[ A_{m,1} = f(m-1)+1 = (2^{m-1}-1)+1 = 2^{m-1}.\] $2^{1-1} = 1$ であるから, これは $m = 1$ のときも成り立つ. ゆえに, \[ A_{m,n} = A_{m,1}+(n-1)\cdot 1 = 2^{m-1}+n-1.\]
(2)
$[\ast ]$ から, 第 $m$ 群の末項は \[ A_{m,2^{m-1}} = f(m) = 2^m-1.\] よって, 第 $m$ 群の和は, \begin{align*} S_m &\!=\! \frac{2^{m-1}}{2}(A_{m,1}\!\!+\!\!A_{m,2^{m-1}}) \!=\! 2^{m-2}(2^{m-1}\!\!+\!\!(2^m-1)) \\ &\!=\! 2^{m-2}((1+2)2^{m-1}\!\!-\!\!1) \!=\! 2^{m-2}(3\cdot 2^{m-1}\!\!-\!\!1). \end{align*}

問題

群数列

問題≪格子点と自然数の対応(群数列)≫

 $xy$ 平面の各座標が正の整数である点 $(x,\ y)$ を, $x+y$ の小さい方から, 次いで $y$ 座標の小さい方から, 正の整数に小さい順に対応させていく. 点 $(x,\ y)$ に対応する正の整数を $A_{x+y-1,y}$ で表す.
(1)
正の整数 $m$ に対して $A_{m,1}$ を求めよ.
(2)
正の整数 $m,$ $n$ に対して $A_{m,n}$ を求めよ.
(3)
$100$ に対応づけられた点の座標を求めよ.

解答例

(1)
数列 $\{ n\}$ を \[ 1|2,\ 3|4,\ 5,\ 6|7,\ 8,\ 9,\ 10|11,\ \cdots\] のように群に分けると, 第 $m$ 群の第 $n$ 項が $A_{m,n}$ になる.
第 $m$ 群の項数は $m$ だから, 第 $m$ 群の末項までの項数を $f(m)$ とおくと, \[ f(m) = \sum_{k = 1}^mk = \frac{1}{2}m(m+1).\] $m \geqq 2$ のとき, 第 $m$ 群の初項は, \[ A_{m,1} = f(m-1)+1 = \frac{1}{2}(m-1)m+1.\] $\dfrac{1}{2}\cdot 0\cdot 1+1 = 1 = A_{1,1}$ であるから, これは $m = 1$ のときも成り立つ.
(2)
$n \geqq 2$ のとき, \[ A_{m,n} = A_{m,1}+(n-1) = \frac{1}{2}(m-1)m+n \quad \cdots [\ast ].\] これは $n = 1$ のときも成り立つ.
(3)
点 $(x,\ y)$ が $A_{m,n}$ に対応するとき, \[\begin{cases} m = x+y-1, \\ n = y. \end{cases} \quad \therefore\begin{cases} x = m-n+1, \\ y = n. \end{cases}\] そこで, $A_{m,n} = 100$ を満たす正の整数 $m,$ $n$ を求める.
$A_{m,1} \leqq A_{m,n} < A_{m+1,1}$ から, \begin{align*} \frac{1}{2}(m-1)m+1 &\leqq 100 < \frac{1}{2}m(m+1)+1 \\ \therefore (m-1)m &\leqq 198 < m(m+1). \end{align*} $m$ は正の整数であるから, $m = 14.$ $[\ast ]$ から \[ 100 = A_{14,n} = \frac{1}{2}\cdot 13\cdot 14+n\] であるので, $n = 9.$
ゆえに, 求める点の座標は,
$(14-9+1,\ 9)$ すなわち $(6,\ 9).$

問題≪群数列の和≫

(I)
初項 $1,$ 公差 $2$ の等差数列の第 $n$ 項までの和 $s_n$ を求めよ.
(II)
(I) の数列を第 $m$ 群の項数が $m$ となるように区切って得られる群数列 \[ 1|3,\ 5|7,\ 9,\ 11|13,\ 15,\ 17,\ 19|\cdots\] について,
(1)
第 $m$ 群の末項までの項数 $f(m)$ を求めよ.
(2)
第 $m$ 群の第 $n$ 項 $A_{m,n}$ を求めよ.
(3)
第 $m$ 群の和 $S_m$ を求めよ.
(4)
$\sum\limits_{k = 1}^mk^3 = \left(\sum\limits_{k = 1}^mk\right) ^2$ が成り立つことを示せ.

解答例

(I)
\[ s_n = \frac{n}{2}(1+(2n-1)) = n^2.\]
(II)
(1)
\[ f(m) = \sum\limits_{k = 1}^mk = \frac{1}{2}m(m+1).\]
(2)
$m > 1$ のとき, 第 $m$ 群の初項までの項数は, \[ f(m-1)+1 = \frac{1}{2}(m-1)m+1.\] $\dfrac{1}{2}\cdot 0\cdot 1+1 = 1$ から, これは $m = 1$ のときも成り立つ. よって, 第 $m$ 群の初項は \[ A_{m,1} = 2\left(\frac{1}{2}(m-1)m\!+\!1\right) \!-\!1 = m^2\!-\!m\!+\!1\] であるから, \[ A_{m,n} = A_{m,1}+(n-1)\cdot 2 = m^2-m+2n-1.\]
(3)
\begin{align*} S_m &= \frac{m}{2}(2A_{m,1}+(m-1)\cdot 2) \\ &= m((m^2-m+1)+(m-1)) = m^3. \end{align*}
(4)
(3) から, 第 $m$ 群の末項までの和は, \[\sum_{k = 1}^nS_k = \sum_{k = 1}^nk^3.\] これは, 数列 $\{ 2n-1\}$ の第 $f(m)$ 項までの和に等しいから, (I) の結果から, \[\sum_{k = 1}^mk^3 = f(m)^2 = \left(\sum_{k = 1}^mk\right) ^2.\]

補足≪立方数の和は平方数の和の平方≫

 $i$ 行 $j$ 列に $ij$ を配置することで $n$ 行 $n$ 列のマスに数を並べる. $i$ 行の和は $\displaystyle\sum_{j = 1}^nij = i\sum_{j = 1}^nj$ であるから, これら $n^2$ 個の数の和は, \[\sum_{i = 1}^n\sum_{j = 1}^nij = \left(\sum_{i = 1}^ni\right)\left(\sum_{j = 1}^nj\right) = \left(\sum_{k = 1}^nk\right) ^2\] である. 一方, $1|2,4,2|3,6,9,6,3|\cdots$ のように逆 $L$ 字型に群に分けると, 第 $k$ 群の和は \begin{align*} &k+2k+3k+\cdots +k^2 \\ &\qquad k+2k+\cdots +k(k-1) \\ &= k\sum_{l = 1}^k(2l-1) \\ &= k\cdot k^2 = k^3 \end{align*} となるから, \[\sum_{k = 1}^nk^3 = \left(\sum_{k = 1}^nk\right) ^2\] が成り立つ.

その他

問題≪席替えで同じ席にならない確率≫

 $n$ 人のクラスで席替えをするとき, 全員が前と同じ席にならない場合の数を $a_n,$ 確率を $p_n$ とおく.
(1)
$a_{n+2} = (n+1)(a_{n+1}+a_n)$ が成り立つことを示せ.
(2)
$n > 2$ のとき, $p_n-p_{n-1} = -\dfrac{1}{n}(p_{n-1}-p_{n-2})$ が成り立つことを示せ.
(3)
数列 $\{ p_n\}$ の一般項を求めよ.

解答例

(1)
$n+2$ 人のクラスの席替えを考える. 特定の人物 A, 残った $n+1$ 人の順に行っても場合の数は同じである. A が移動する方法は $n+1$ 通り. A の移動先にいる人物を B として, 一旦 A と B の席を入れ替える.
(i)
最終的に A と B が入れ替わらない場合. この状態から A 以外の $n+1$ 人が同じ席にならないように移動すれば良い. その方法は $a_{n+1}$ 通り.
(ii)
最終的に A と B が入れ替わったままの場合. 残りの $n$ 人が同じ席にならないように移動すれば良い. その方法は $a_n$ 通り.
(i), (ii) は排反だから, $$a_{n+2} = (n+1)(a_{n+1}+a_n).$$
(2)
$n$ 人が席替えをする方法は $n!$ 通りあるから, $$p_n = \frac{a_n}{n!}.$$ (1) より, $n > 2$ のとき, \begin{align*} p_n &= \frac{(n-1)(a_{n-1}+a_{n-2})}{n!} \\ &= \frac{n-1}{n}\cdot\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\cdot\frac{a_{n-2}}{(n-2)!} \quad \\ &= \left( 1-\frac{1}{n}\right) p_{n-1}+\frac{1}{n}p_{n-2}. \\ \therefore p_n-p_{n-1} &= -\frac{1}{n}(p_{n-1}-p_{n-2}) \quad \cdots [n]. \end{align*}
(3)
$[n]$ より, \begin{align*} p_{n-1}-p_{n-2} &= -\frac{1}{n-1}(p_{n-2}-p_{n-3}) \quad \cdots [n-1], \\ &\vdots \\ p_3-p_2 &= -\frac{1}{3}(p_2-p_1) \quad \cdots [3]. \end{align*} $p_1 = \dfrac{0}{1!} = 0,$ $p_2 = \dfrac{1}{2!} = \dfrac{1}{2}$ より $p_2-p_1 = \dfrac{1}{2} \neq 0$ だから, 帰納法より, $$p_n-p_{n-1} \neq 0.$$ $[n],$ $[n-1],$ $\cdots,$ $[3]$ の辺々を掛け合わせて $p_k-p_{k-1}\ (3 \leqq k \leqq n-1)$ で割ると, $$p_n-p_{n-1} = (-1)^{n-2}\frac{p_2-p_1}{n(n-1)\cdots 3} = \frac{(-1)^n}{n!}.$$ これは $n > 1$ に対して成り立つ. ゆえに, $$p_1 = 0, \quad p_n = \sum\limits_{k = 2}^n\frac{(-1)^k}{k!}\ (n > 1).$$

解説

(1)
$1,$ $\cdots,$ $n$ の順列で $1 \leqq k \leqq n$ なる各整数 $k$ に対して $k$ 番目が $k$ でない順列を完全順列または攪乱順列(derangement)と呼び, その総数 $n!p_n$ をモンモール数(Montmort number)と呼ぶ.
(2)
$0! = 1$ と定義すれば, $n = 1$ の場合を含めて $p_n = \sum\limits_{k = 0}^n\dfrac{(-1)^k}{k!}$ と表せる.
(3)
$n$ が大きくなるにつれて, $p_n$ はある一定の値 $p = 0.36787\cdots$ に限りなく近づく: \begin{align*} p_3 &= \frac{1}{3} = 0.\dot 3, & p_4 &= \frac{3}{8} = 0.375, \\ p_5 &= \frac{11}{30} = 0.3\dot 6, & p_6 &= \frac{53}{144} = 0.3680\dot 5,\ \cdots. \end{align*} この $p$ を数列 $\{ p_n\}$ の極限値と呼び, $\lim\limits_{n \to \infty}p_n = \sum\limits_{n = 0}^\infty\dfrac{(-1)^n}{n!} = p$ と表す(数学 III). $p$ はネイピアの数と呼ばれる無理数 $e$ の逆数であることが知られている. より一般に, 指数関数のテイラー展開の公式 $e^x = \sum\limits_{n = 0}^\infty\dfrac{x^n}{n!}$ が成り立つ(大学以降).

問題≪特殊な等式を満たす数列の決定≫

 数列 $\{ a_n\}$ が $a_k < a_{k+1}\ (k \geqq 1)$ と \[ a_{kl} = a_k+a_l \quad (k \geqq 1,\ l \geqq 1)\] を満たすとする.
(1)
$k,$ $l$ を $2$ 以上の整数とする. 正の整数 $n$ が与えられたとき, \[ l^{m-1} \leqq k^n < l^m \quad \cdots [\ast ]\] を満たす正の整数 $m$ が存在することを示せ.
(2)
$k,$ $l$ を $2$ 以上の整数とするとき, \[ -\frac{1}{n} < \frac{a_k}{a_l}-\frac{\log k}{\log l} < \frac{1}{n} \quad (n \geqq 1)\] が成り立つことを示せ.
(3)
$\{ a_n\}$ の一般項を $a_2$ を用いて表せ.
[九州大 2003]

解答例

(1)
(i)
$k^n < l$ のとき. $m = 1$ とすれば良い.
(ii)
$l \leqq k^n$ のとき. $l^x$ の単調増加性により, $l^x$ が初めて $k^n$ より大きくなるような整数 $x$ が存在するので, それを $m$ とすれば良い.
(2)
$a_{k^n} = a_{k^{n-1}}+a_k$ であるから, 数学的帰納法により \[ a_{k^n} = na_k \quad \cdots [1]\] となる. (1) から $[\ast ]$ を満たす正の整数 $m$ をとると, $\{ a_n\}$ の単調増加性により \[ a_{l^{m-1}} \leqq a_{k^n} < a_{l^m} \quad \cdots [2]\] となる. よって, $[1],$ $[2]$ から, \[ (m-1)a_l \leqq na_k < ma_l\] となり, \[ m-1 \leqq \frac{na_k}{a_l} < m \quad \cdots [3]\] となる. また, $[\ast ]$ の辺々の自然対数をとると \[ (m-1)\log l \leqq n\log k < m\log l\] となるから, \[ m-1 \leqq \frac{n\log k}{\log l} < m \quad \cdots [4]\] となる. $[3],$ $[4]$ の辺々を引くと, \[ -\frac{1}{n} < \frac{a_k}{a_l}-\frac{\log k}{\log l} < \frac{1}{n} \quad \cdots [5]\] が得られる.
(3)
$k,$ $l$ を $2$ 以上の整数とする. $\lim\limits_{n \to \infty}\dfrac{\pm 1}{n} = 0$ であるから, $[5]$ に挟みうちの原理を適用すると, \[\frac{a_k}{a_l} = \frac{\log k}{\log l}.\] よって, \[\frac{a_k}{\log k} = \frac{a_l}{\log l}\] となるが, $l$ は $2$ 以上の任意の整数だから \[\frac{a_k}{\log k} = \frac{a_2}{\log 2}\] となり, \[ a_k = a_2\frac{\log k}{\log 2} = a_2\log _2k \quad \cdots [6]\] となる. また, \[ a_1 = a_{1\cdot 1} = a_1+a_1\] から $a_1 = 0$ となるが, これは $[6]$ を満たす.
ゆえに, $\{ a_n\}$ の一般項は $[6]$ で与えられる.

問題≪シルベスター数列とエジプト分数≫

 $a_1 = 2,$ $a_{n+1} = 1+a_1\cdots a_n$ で数列 $\{ a_n\}$ を定める. ここで, $a_1\cdots a_n$ は $\{ a_n\}$ の初項から第 $n$ 項までの積を表す.
(A)
\[\frac{1}{a_1}+\cdots +\frac{1}{a_n} = 1-\frac{1}{a_1\cdots a_n} \quad \cdots [\ast ]\] が成り立つことを示せ.
(B)
$a_{n+1} = a_n{}^2-a_n+1$ が成り立つことを示せ.

解答例

(A)
(i)
$1-\dfrac{1}{a_1} = 1-\dfrac{1}{2} = \dfrac{1}{2} = \dfrac{1}{a_1}$ から, $[\ast ]$ は$n = 1$ のとき成り立つ.
(ii)
与えられた正の整数 $n$ に対して $[\ast ]$ が成り立つとする. このとき, $[\ast ]$ の両辺に $\dfrac{1}{a_{n+1}}$ を加えると, \begin{align*} \frac{1}{a_1}+\cdots +\frac{1}{a_n}+\frac{1}{a_{n+1}} &= 1-\frac{1}{a_1\cdots a_n}+\frac{1}{a_{n+1}} \\ &= 1-\frac{a_{n+1}-a_1\cdots a_n}{a_1\cdots a_na_{n+1}} \\ &= 1-\frac{1}{a_1\cdots a_na_{n+1}} \end{align*} となり, $[\ast ]$ において $n$ を $n+1$ に置き換えた等式が得られる.
(i), (ii)から, すべての正の整数 $n$ に対して $[\ast ]$ が成り立つ.
(B)
準備中.