数学的帰納法
数学的帰納法
定理《数学的帰納法》
正の整数 $n$ に関する命題 $p(n)$ について,
- (i)
- $p(1)$ は真である
- (ii)
- $p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
証明
命題 $p(n+1)$ が真であるような非負整数 $n$ 全体の集合 $S$ に,「数学的帰納法の原理」と呼ばれる, 次の自然数論の公理を適用することで示される:
非負整数全体の集合 $\mathbb N$ の空でない部分集合 $S$ について,
- (i)
- $0 \in S$ は真である
- (ii)
- $n \in S$ $\Longrightarrow$ $n+1 \in S$ は真である
問題《多変数版のベルヌーイの不等式》
次のことを示せ.
- (1)
- すべての正の整数 $n$ に対して, \[ (1+x_1)\cdots (1+x_n) \geqq 1+\sum_{k = 1}^nx_k \quad (x_k \geqq 0) \quad \cdots [1]\] が成り立つ.
- (2)
- すべての正の整数 $n$ に対して, \[ (1+x)^n \geqq 1+nx \quad (x \geqq 0) \quad \cdots [2]\] が成り立つ.
解答例
- (1)
- (i)
- $n = 1$ のとき. $(1+x_1)^1 = 1+x_1$ から, $[1]$ が成り立つ.
- (ii)
- $n = m$ ($m$: 正の整数) のとき $[1]$ が成り立つとする. $x_1,$ $\cdots,$ $x_m,$ $x_{m+1} \geqq 0$ のとき, $[1]$ の両辺に $1+x_{m+1}\,(\geqq 0)$ を掛けると, \[\begin{aligned} &(1+x_1)\cdots (1+x_m)(1+x_{m+1}) \\ &\geqq \left( 1+\sum_{k = 1}^mx_k\right) (1+x_{m+1}) \\ &= 1+\sum_{k = 1}^mx_k+x_{m+1}+x_{m+1}\sum_{k = 1}^mx_k \\ &\geqq 1+\sum_{k = 1}^{m+1}x_k \quad \left(\because x_{m+1}\sum_{k = 1}^mx_k \geqq 0\right) \end{aligned}\] となり, $n = m+1$ のとき $[1]$ が成り立つ.
- (2)
- $[1]$ において $x_1 = \cdots = x_n = x$ とすると, $[2]$ が得られる.
参考
問題《階乗進法にまつわる恒等式》
すべての正の整数 $n$ に対して
\[\sum_{k = 1}^nk\cdot k! = (n+1)!-1 \quad \cdots [\ast ]\]
が成り立つことを示せ.
解答例
- (i)
- $n = 1$ のとき. $1\cdot 1! = 2!-1 = 1$ から, $[\ast ]$ が成り立つ.
- (ii)
- $n = m$ ($m$: 正の整数) のとき $[\ast ]$ が成り立つとする. このとき, \[\begin{aligned} \sum_{k = 1}^{m+1}k\cdot k! &= \sum_{k = 1}^mk\cdot k!+(m+1)\cdot (m+1)! \\ &= (m+1)!-1+(m+1)\cdot (m+1)! \\ &= \{ 1+(m+1)\}\cdot (m+1)!-1 \\ &= (m+2)!-1 \end{aligned}\] となり, $n = m+1$ のとき $[\ast ]$ が成り立つ.
別解
各正の整数 $n$ に対して
\[ k\cdot k! = \{ (k+1)-1\}\cdot k! = (k+1)!-k! \quad (1 \leqq k \leqq n)\]
であるから,
\[\sum_{k = 1}^nk\cdot k! = \sum_{k = 1}^n\{ (k+1)!-k!\} = (n+1)!-1\]
が成り立つ.
参考
正の整数 $d$ に対して, $(d+1)!$ 未満のすべての非負整数は $k$ 以下の非負整数 $a_k$ $(1 \leqq k \leqq d)$ を用いて
\[\sum_{k = 1}^da_kk!\]
の形にただ $1$ 通りに表されることが, 等式 $[\ast ]$ により示される.
このような数の表し方を「階乗進法」(factorial number system) と呼ぶ.
一般化された数学的帰納法
定理《一般化された数学的帰納法》
$m$ を整数, $r$ を正の整数とする.
- (1)
- $m$ 以上の整数 $n$ に関する命題 $p(n)$ について,
- (i)
- $p(m)$ は真である
- (ii)
- $p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
- (2)
- $m$ 以上の整数 $n$ に関する命題 $p(n)$ について,
- (i)
- $p(m),$ $\cdots,$ $p(m+r-1)$ は真である
- (ii)
- $p(n),$ $\cdots,$ $p(n+r-1)$ $\Longrightarrow$ $p(n+r)$ は真である
- (3)
- $m$ 以上の整数 $n$ に関する命題 $p(n)$ について,
- (i)
- $p(m)$ は真である
- (ii)
- $p(m),$ $\cdots,$ $p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
証明
- (1)
- 正の整数 $n$ に関する命題 $q(n) = p(m+n-1)$ に $m = 1$ の場合の数学的帰納法を適用することで示される.
- (2)
- “$p(n),$ $\cdots,$ $p(n+r-1)$ $\Longrightarrow$ $p(n+r)$” は “$p(n),$ $\cdots,$ $p(n+r-1)$ $\Longrightarrow$ $p(n+1),$ $\cdots,$ $p(n+r)$” と同値であるから, 命題 “$p(n),$ $\cdots,$ $p(n+r-1)$” に (1) を適用することで, (i), (ii) のときすべての $n$ に対して $p(n)$ が真であることが示される.
- (3)
- “$p(m),$ $\cdots,$ $p(n)$ $\Longrightarrow$ $p(n+1)$” は “$p(m),$ $\cdots,$ $p(n)$ $\Longrightarrow$ $p(m),$ $\cdots,$ $p(n+1)$” と同値であるから, 命題 “$p(m),$ $\cdots,$ $p(n)$” に (1) を適用することで, (i), (ii) のときすべての $n$ に対して $p(n)$ が真であることが示される.
問題《$2^n$ と $n^2$ の比較》
正の整数 $n$ に対して, $n^2$ と $2^n$ の大小を比較せよ.
解答例
$1 \leqq n \leqq 10$ において $n^2,$ $2^n$ の値は次の表の通りである.
そこで, $5$ 以上のすべての整数 $n$ に対して
\[ n^2 < 2^n \quad \cdots [1]\]
が成り立つことを示す.
である.
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
| $n^2$ | $1$ | $4$ | $9$ | $16$ | $25$ | $36$ | $49$ | $64$ | $81$ | $100$ |
| $2^n$ | $2$ | $4$ | $8$ | $16$ | $32$ | $64$ | $128$ | $256$ | $512$ | $1024$ |
- (i)
- $n = 5$ のとき. 表から, $[1]$ が成り立つ.
- (ii)
- $n = k$ ($k$: $5$ 以上の整数) のとき $[1]$ が成り立つとする. このとき, \[\begin{aligned} 2^{k+1}-(k+1)^2 &= 2\cdot 2^k-(k^2+2k+1) \\ &= 2(2^k-k^2)+(k^2-2k-1) \\ &= 2(2^k-k^2)+(k-1)^2-2 \\ &> 2\cdot 0+(4-1)^2-2 \quad (\because k > 4) \\ &= 7 > 0 \end{aligned}\] となるから, $n = k+1$ のとき $[1]$ が成り立つ.
| $n = 1,$ $n \geqq 5$ のとき | $n^2 < 2^n,$ |
| $n = 2,$ $4$ のとき | $n^2 = 2^n,$ |
| $n = 3$ のとき | $n^2 > 2^n$ |
参考
問題《$2$ 次方程式の解のべき乗和で表される整数》
$x^2-x-1 = 0$ の $2$ つの解を $x = \alpha,$ $\beta$ $(\alpha > \beta )$ とおき,
各正の整数 $n$ に対して $L_n = \alpha ^n+\beta ^n$ とおく.
- (1)
- $L_n,$ $L_{n+1}$ を用いて $L_{n+2}$ を表せ.
- (2)
- すべての正の整数 $n$ に対して $L_n$ は整数であることを示せ.
解答例
- (1)
- $\alpha = \dfrac{1+\sqrt 5}{2},$ $\beta = \dfrac{1-\sqrt 5}{2}$ から \[\begin{aligned} \alpha +\beta &= \frac{1+\sqrt 5}{2}+\frac{1-\sqrt 5}{2} = 1, \\ \alpha\beta &= \frac{1+\sqrt 5}{2}\cdot\frac{1-\sqrt 5}{2} = -1 \end{aligned}\] であるので, \[\begin{aligned} L_{n+2} &= \alpha ^{n+2}+\beta ^{n+2} \\ &= (\alpha ^{n+1}+\beta ^{n+1})(\alpha +\beta )-\alpha\beta (\alpha ^n+\beta ^n) \\ &= (\alpha ^{n+1}+\beta ^{n+1})\cdot 1-(-1)\cdot (\alpha ^n+\beta ^n) \\ &= (\alpha ^n+\beta ^n)+(\alpha ^{n+1}+\beta ^{n+1}) \\ &= L_n+L_{n+1} \end{aligned}\] が成り立つ.
- (2)
- (i)
- \[\begin{aligned} L_1 &= \alpha +\beta = 1, \\ L_2 &= \alpha ^2+\beta ^2 = (\alpha +\beta )^2-2\alpha\beta \\ &= 1^2-2\cdot (-1) = 3 \end{aligned}\] であるから, $L_1,$ $L_2$ は整数である.
- (ii)
- 与えられた正の整数 $n$ に対して, $L_n,$ $L_{n+1}$ が整数であるとすると, 整数の和 \[ L_n+L_{n+1} = L_{n+2}\] も整数となる.
参考
$L_1 = 1,$ $L_2 = 3,$ $L_{n+2} = L_n+L_{n+1}$ で定まる数列 $\{ L_n\}$ を「リュカ数列」(Lucas sequence) と呼ぶ.
一般に, $L_n$ は
\[ L_n = \left(\frac{1+\sqrt 5}{2}\right) ^n+\left(\frac{1-\sqrt 5}{2}\right) ^n\]
と表されることが知られている.
定義により, $L_n$ は整数である.
問題《カッシーニの公式》
数列 $\{ F_n\}$ について, 初期条件 $F_1 = F_2 = 1$ のもとで,
- $[1]$
- $F_{n+2} = F_n+F_{n+1}$
- $[2]$
- $F_{n+1}{}^2-F_nF_{n+2} = (-1)^n$
(参考: $2001$ 横浜国立大)
解答例
まず, $[1]$ を仮定して, $[2]$ を数学的帰納法で示す.
次に, $[2]$ を仮定して, $[1]$ と $F_n > 0$ を数学的帰納法で示す.
ゆえに, $[1],$ $[2]$ は同値である.
- (i)
- $n = 1$ のとき. \[ F_2{}^2-F_1F_3 = 1^2-1\cdot (1+1) = -1\] から, $[2]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 正の整数) のとき $[2]$ が成り立つとする. このとき, \[\begin{aligned} F_{k+2}{}^2-F_{k+1}F_{k+3} &= F_{k+2}{}^2-F_{k+1}(F_{k+1}+F_{k+2}) \\ &= F_{k+2}{}^2-F_{k+1}{}^2-F_{k+1}F_{k+2} \\ &= F_{k+2}{}^2-F_{k+1}{}^2-(F_{k+2}-F_k)F_{k+2} \\ &= F_{k+2}{}^2-F_{k+1}{}^2-F_{k+2}{}^2+F_kF_{k+2} \\ &= -(F_{k+1}{}^2-F_kF_{k+2}) \\ &= -(-1)^k = (-1)^{k+1} \end{aligned}\] となるから, $n = k+1$ のとき $[2]$ が成り立つ.
次に, $[2]$ を仮定して, $[1]$ と $F_n > 0$ を数学的帰納法で示す.
- (i)
- $n = 1,$ $2$ のとき. $[2]$ に $n = 1$ を代入すると $1^2-1\cdot F_3 = -1$ から $F_3 = 2 = 1+1 = F_1+F_2$ となり, $[2]$ に $n = 2$ を代入すると $2^2-1\cdot F_4 = 1$ から $F_4 = 3 = 1+2 = F_2+F_3$ となるので, $[1]$ が成り立つ. また, $F_1 = F_2 = 1 > 0$ が成り立つ.
- (ii)
- $n = k,$ $k+1$ ($k$: 正の整数) のとき, $[1]$ と $F_n > 0$ が成り立つとする. \[\begin{aligned} F_{k+2}{}^2-F_{k+1}F_{k+3} &= (-1)^{k+1}, \\ F_{k+1}{}^2-F_kF_{k+2} &= (-1)^k \end{aligned}\] の辺々を加えると \[\begin{aligned} F_{k+2}{}^2+F_{k+1}{}^2-F_{k+1}F_{k+3}-F_kF_{k+2} &= 0 \\ F_{k+2}{}^2\!+\!F_{k+1}{}^2\!-\!F_{k+1}F_{k+3}\!-\!(F_{k+2}\!-\!F_{k+1})F_{k+2} &= 0 \\ F_{k+1}{}^2+F_{k+1}F_{k+2}-F_{k+1}F_{k+3} &= 0 \\ F_{k+1}(F_{k+1}+F_{k+2}-F_{k+3}) &= 0 \end{aligned}\] となるから, $F_{k+1} > 0$ に注意すると $F_{k+1}+F_{k+2}-F_{k+3} = 0$ となり, $n = k+1$ のとき $[1]$ が成り立つ. また, $F_{k+2} = F_k+F_{k+1} > 0$ が成り立つ.
ゆえに, $[1],$ $[2]$ は同値である.
参考
- 初期条件 $F_1 = F_2 = 1$ と漸化式 $[1]$ で定まる数列 $\{ F_n\}$ は「フィボナッチ数列」(Fibonacci sequence) と呼ばれ, $[1]$ と同値な漸化式 $[2]$ は「カッシーニの公式」(Cassini's identity) として知られている.
- 初期条件 $P_1 = 1,$ $P_2 = 2$ と漸化式 $P_{n+2} = 2P_{n+1}+P_n$ で定まる「ペル数列」(Pell sequence) $\{ P_n\}$ についても, 同様の漸化式 $P_{n+1}{}^2-P_nP_{n+2} = (-1)^n$ の成り立つことが知られている.
問題《フィボナッチ数列の加法定理と $2$ 倍公式》
$m,$ $n$ を非負整数とする.
\[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\]
により定まる数列 $\{ F_n\}$ について, 次のことを示せ.
- (1)
- $F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}\ \cdots [*]$ が成り立つ.
- (2)
- $n \geqq 1$ のとき, $F_{2n} = F_{n+1}{}^2-F_{n-1}{}^2,$ $F_{2n+1} = F_n{}^2+F_{n+1}{}^2$ が成り立つ.
解答例
- (1)
- $m$ を固定して, $n$ に関する数学的帰納法で $[*]$ を示す.
- (i)
- $n = 0,$ $1$ のとき. $F_0 = 0,$ $F_1 = 1,$ $F_2 = 0+1 = 1$ から \[\begin{aligned} &F_mF_0+F_{m+1}F_1 = F_{m+1}, \\ &F_mF_1+F_{m+1}F_2 = F_m+F_{m+1} = F_{m+2} \end{aligned}\] であるので, $[*]$ が成り立つ.
- (ii)
- $n = k,$ $k+1$ ($k$: 非負整数) のとき $[*]$ が成り立つとする. このとき, \[\begin{aligned} &F_{m+k+3} \\ &= F_{m+k+1}+F_{m+k+2} \\ &= F_mF_k+F_{m+1}F_{k+1}+F_mF_{k+1}+F_{m+1}F_{k+2} \\ &= F_m(F_k+F_{k+1})+F_{m+1}(F_{k+1}+F_{k+2}) \\ &= F_mF_{k+2}+F_{m+1}F_{k+3} \end{aligned}\] となり, $n = k+2$ のとき $[*]$ が成り立つ.
- (2)
- $[*]$ において, $m = n-1$ とすると \[\begin{aligned} F_{2n} &= F_{n-1}F_n+F_nF_{n+1} = (F_{n+1}+F_{n-1})F_n \\ &= (F_{n+1}+F_{n-1})(F_{n+1}-F_{n-1}) = F_{n+1}{}^2-F_{n-1}{}^2 \end{aligned}\] が得られ, $m = n$ とすると \[ F_{2n+1} = F_n{}^2+F_{n+1}{}^2\] が得られる.
参考
- 「フィボナッチ数列」$\{ F_n\}$ の多くの性質が等式 \[ F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1} \quad (m \geqq 0,\ n \geqq 0) \quad \cdots [*]\] から導かれる (こちらも参照). $m$ を $m-1$ で置き換えると, この等式は \[ F_{m+n} = F_{m-1}F_n+F_mF_{n+1} \quad (m \geqq 1,\ n \geqq 0) \quad \cdots [*]'\] と同値であるから, $[*],$ $[*]'$ は「フィボナッチ数列の加法定理」(addition theorem) と呼ばれる.
- 等式 $F_{2n} = F_{n+1}{}^2-F_{n-1}{}^2,$ $F_{2n+1} = F_n{}^2+F_{n+1}{}^2$ を使うと,「フィボナッチ数列」の番号の大きい項が容易に求められる.
- 「フィボナッチ数列」$\{ F_n\},$「リュカ数列」$\{ L_n\}$ ($L_1 = 1,$ $L_2 = 3,$ $L_{n+2} = L_n+L_{n+1}$ で定まる数列) について, \[ 2F_{m+n} = F_mL_n+L_mF_n, \quad 2L_{m+n} = 5F_mF_n+L_mL_n\] が成り立つ. これらも「フィボナッチ数列の加法定理」「リュカ数列の加法定理」として知られている.
問題《立方の和と和の平方が等しい数列》
正の数からなる数列 $\{ a_n\}$ が
\[ a_1{}^3+\cdots +a_n{}^3 = (a_1+\cdots +a_n)^2 \quad \cdots [1]\]
を満たすとする.
このとき,
\[ a_n = n \quad \cdots [2]\]
であることを示せ.
解答例
- (i)
- $n = 1$ のとき. $[1]$ つまり $a_1{}^3 = a_1{}^2,$ $a_1{}^2(a_1-1) = 0$ と $a_1 > 0$ から, $a_1 = 1$ であり, $[2]$ が成り立つ.
- (ii)
- $n \leqq k$ ($k$: 正の整数) のとき $[2]$ が成り立つとする. このとき, \[\begin{aligned} &(1+\cdots +k)^2 = (a_1+\cdots +a_k)^2 \\ &= a_1{}^3+\cdots +a_k{}^3 = 1^3+\cdots +k^3 \end{aligned}\] であるので, $[1]$ に $n = k+1$ を代入して得られる関係式 \[ a_1{}^3+\cdots +a_k{}^3+a_{k+1}{}^3 = (a_1+\cdots +a_k+a_{k+1})^2\] から \[\begin{aligned} &1^3+\cdots +k^3+a_{k+1}{}^3 = (1+\cdots +k+a_{k+1})^2 \\ &= (1+\cdots +k)^2+2(1+\cdots +k)a_{k+1}+a_{k+1}{}^2 \\ &= (1^3+\cdots +k^3)+k(k+1)a_{k+1}+a_{k+1}{}^2 \end{aligned}\] が得られる. 最後の等号では $1+\cdots +k = \dfrac{1}{2}k(k+1)$ を使った. よって, \[\begin{aligned} a_{k+1}{}^3-a_{k+1}{}^2-k(k+1)a_{k+1} &= 0 \\ a_{k+1}(a_{k+1}+k)\{ a_{k+1}-(k+1)\} &= 0 \end{aligned}\] が成り立つので, $a_{k+1} > 0$ から $a_{k+1} = k+1$ であり, $n = k+1$ のとき $[2]$ が成り立つ.
参考
- 本問で示した通り, \[\sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+1)^2 = \left(\sum_{k = 1}^nk\right) ^2\] が成り立つ.
- すべての正の整数 $m$ に対して
\[ S_m(n) = \sum_{k = 1}^nk^m \quad (n \geqq 1)\]
を満たす多項式 $S_m(x)$ が存在する (こちらを参照).
この多項式について, 次のことが知られている (こちらを参照).
- (i)
- $m$ が偶数のとき. $S_m(x)$ は $S_2(x)$ で割り切れて, その商は $S_1(x)$ の多項式として表される.
- (ii)
- $m$ が奇数のとき. $S_m(x)$ は $S_1(x)$ の多項式として表され, $m \geqq 3$ ならば $S_1(x)^2$ で割り切れる.
問題《ゼッケンドルフの定理》
$F_1 = F_2 = 1,$ $F_{n+2} = F_n+F_{n+1}$ で定まる数列 $\{ F_n\}$ を「フィボナッチ数列」と呼ぶ.
すべての正の整数 $n$ に対して,
- $[*]$
- $n$ は「フィボナッチ数列」の隣り合わない項の和として表せる
(参考: $2017$ 九州大)
解答例
- (i)
- $n = 1$ のとき. $1 = F_1$ であるから, $[*]$ が成り立つ.
- (ii)
- 与えられた正の整数 $k$ について $k$ 未満のすべての正の整数 $n$ に対して $[*]$ が成り立つとする.
定義から $\{ F_n\}$ は $n \geqq 2$ において単調増加であって正の整数を値にとるので, $F_m \leqq k < F_{m+1}$ なる $2$ 以上の番号 $m$ が存在する.
- $F_m = k$ のとき. $k$ は「フィボナッチ数列」の項そのものである.
- $F_m < k$ のとき. $k-F_m < k$ であるので, 数学的帰納法の仮定から, $S = k-F_m$ は「フィボナッチ数列」の隣り合わない項の和として表せる. $k-F_m < F_{m+1}-F_m = F_{m-1}$ であるから, それらの項は番号が $m-2$ 以下の項であり, $F_m$ と異なる. よって, $k = S+F_m$ は「フィボナッチ数列」の隣り合わない項の和として表せる.
参考
- すべての正の整数は「フィボナッチ数列」の隣り合わない項 (第 $2$ 項以降) の和としてただ $1$ 通りに表される. このことは「ゼッケンドルフの定理」(Zeckendorf's theorem) として知られている. 例えば, \[\begin{aligned} 1 &= F_2, & 7 &= F_5+F_3, \\ 2 &= F_3, & 8 &= F_6, \\ 3 &= F_4, & 9 &= F_6+F_2, \\ 4 &= F_4+F_2, & 10 &= F_6+F_3, \\ 5 &= F_5, & 11 &= F_6+F_4, \\ 6 &= F_5+F_2, & 12 &= F_6+F_4+F_2 \end{aligned}\] である.
- すべての正の整数は \[ L_0 = 2, \quad L_1 = 1, \quad L_{n+2} = L_n+L_{n+1}\] で定まる「リュカ数列」の隣り合わない項 (第 $0$ 項以降) の和としてただ $1$ 通りに表すこともできる (証明は同様).
問題《$1$ 人飛ばしの継子立て》
出席番号が $1$ 番から $n$ 番までの $n$ 人の生徒が順に $1$ つの輪を作るように並んでいる.
出席番号が $2$ 番の生徒から $1$ 人飛ばしで $1$ 人ずつ輪から抜けていき, 最後に残った生徒の出席番号を $f(n)$ とおく.
次のことを示せ.
ただし, $1$ 人飛ばしというルールは, 各時点で残っている生徒に対して考える.
- (1)
- $f(2n) = 2f(n)-1,$ $f(2n+1) = 2f(n)+1$ が成り立つ.
- (2)
- $n = 2^m+r$ ($m$: 非負整数, $0 \leqq r < 2^m$) のとき, $f(n) = 2r+1$ である.
(参考: $2007$ 鳥取大)
解答例
- (1)
- 生徒が $2n$ 人の場合. $n$ 人が輪から抜けたとき, 出席番号が \[ 1,\ \cdots,\ 2k-1,\ \cdots,\ 2n-1\] の $n$ 人の生徒が残っている. 最後の $1$ 人になるまで操作を続けると, このうちの $f(n)$ 番目の生徒が最後に残るから, その生徒の出席番号は \[ f(2n) = 2f(n)-1\] である.
- 生徒が $2n+1$ 人の場合. $n+1$ 人が輪から抜けたとき, 出席番号が \[ 3,\ \cdots,\ 2k+1,\ \cdots,\ 2n+1\] の $n$ 人の生徒が残っている. 最後の $1$ 人になるまで操作を続けると, このうちの $f(n)$ 番目の生徒が最後に残るから, その生徒の出席番号は \[ f(2n+1) = 2f(n)+1\] である.
- (2)
- $n = 2^m+r$ ($m$: 非負整数, $0 \leqq r < 2^m$) のとき
\[ f(n) = 2r+1 \quad \cdots [*]\]
が成り立つことを $n$ に関する数学帰納法で示す.
- (i)
- $f(1) = 1 = 2\cdot 0+1$ であるから, $n = 1$ のとき $[*]$ が成り立つ.
- (ii)
- $n > 1$ として, $n$ 未満のすべての正の整数に対して $[*]$ が成り立つとする.
- $n$ が偶数の場合. $r$ は偶数であり, \[\frac{n}{2} = 2^{m-1}+\frac{r}{2}\] であるから, \[\begin{aligned} f(n) &= f\left( 2\cdot\frac{n}{2}\right) \\ &= 2f\left(\frac{n}{2}\right) -1 \quad (\because (1)) \\ &= 2\left( 2\cdot\frac{r}{2}+1\right) -1 = 2r+1 \end{aligned}\] が成り立つ.
- $n$ が偶数の場合. $r$ は奇数であり, \[\frac{n-1}{2} = 2^{m-1}+\frac{r-1}{2}\] であるから, \[\begin{aligned} f(n) &= f\left( 2\cdot\frac{n-1}{2}+1\right) \\ &= 2f\left(\frac{n-1}{2}\right) +1 \quad (\because (1)) \\ &= 2\left( 2\cdot\frac{r-1}{2}+1\right) +1 = 2r+1 \end{aligned}\] が成り立つ.
参考
円形に並んだ $n$ 人から $p$ 番隣の人を順に除いていくときに最後に残る人を決定する問題は「継子立て」または「ヨセフスの問題」(Josephus problem) と呼ばれる.
本問では最も簡単な $p = 2$ の場合を考えた.