有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

数学的帰納法

数学的帰納法

定理《数学的帰納法》

 正の整数 $n$ に関する命題 $p(n)$ について,
(i)
$p(1)$ は真である
(ii)
$p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
が成り立つとき, すべての正の整数 $n$ に対して $p(n)$ は真である.

証明

 命題 $p(n+1)$ が真であるような非負整数 $n$ 全体の集合 $S$ に,「数学的帰納法の原理」と呼ばれる, 次の自然数論の公理を適用することで示される: 非負整数全体の集合 $\mathbb N$ の空でない部分集合 $S$ について,
(i)
$0 \in S$ は真である
(ii)
$n \in S$ $\Longrightarrow$ $n+1 \in S$ は真である
が成り立つならば, $S = \mathbb N$ である.

問題《多変数版のベルヌーイの不等式》

 次のことを示せ.
(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]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[1]$ が成り立つ.
(2)
$[1]$ において $x_1 = \cdots = x_n = x$ とすると, $[2]$ が得られる.

参考

 $[2]$ は「ベルヌーイの不等式」(Bernoulli's inequality)として知られている(こちらこちらも参照).
(最終更新日: $2022/04/09$)

一般化された数学的帰納法

定理《一般化された数学的帰納法》

 $m$ を整数, $r$ を正の整数とする.
(1)
$m$ 以上の整数 $n$ に関する命題 $p(n)$ について,
(i)
$p(m)$ は真である
(ii)
$p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
が成り立つとき, $m$ 以上のすべての整数 $n$ に対して $p(n)$ は真である.
(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)$ は真である
が成り立つとき, $m$ 以上のすべての整数 $n$ に対して $p(n)$ は真である.
(3)
$m$ 以上の整数 $n$ に関する命題 $p(n)$ について,
(i)
$p(m)$ は真である
(ii)
$p(m),$ $\cdots,$ $p(n)$ $\Longrightarrow$ $p(n+1)$ は真である
が成り立つとき, $m$ 以上のすべての整数 $n$ に対して $p(n)$ は真である.

証明

(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$ の値は次の表の通りである.
$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$
そこで, $5$ 以上のすべての整数 $n$ に対して \[ n^2 < 2^n \quad \cdots [1]\] が成り立つことを示す.
(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]$ が成り立つ.
(i), (ii) から, $5$ 以上のすべての整数 $n$ に対して $[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 = x^2$ は $2$ つの整数解 $x = 2,$ $4$ をもち(こちらも参照), $-1 < x < 0$ の範囲に $1$ つの実数解をもつ(こちらを参照).
(最終更新日: $2022/04/13$)

問題《$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}\] も整数となる.
(i), (ii) から, すべての正の整数 $n$ に対して $L_n$ は整数である.

参考

 $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]$ を数学的帰納法で示す.
(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]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[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$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[1]$ と $F_n > 0$ が成り立つ.
 ゆえに, $[1],$ $[2]$ は同値である.

参考

 初期条件 $F_1 = F_2 = 1$ と漸化式 $[1]$ で定まる数列 $\{ F_n\}$ は「フィボナッチ数列」(Fibonacci sequence)と呼ばれ, $[1]$ と同値な漸化式 $[2]$ は「カッシーニの公式」(Cassini's identity)として知られている.
(最終更新日: $2022/04/13$)

問題《フィボナッチ数列の加法定理と $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$ のとき $[*]$ が成り立つ.
(i), (ii) から, すべての非負整数 $m,$ $n$ に対して $[*]$ が成り立つ.
(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$ を使うと,「フィボナッチ数列」の番号の大きい項が容易に求められる.
(最終更新日: $2022/06/03$)

問題《立方の和と和の平方が等しい数列》

 正の数からなる数列 $\{ 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]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[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$ で割り切れる.
(最終更新日: $2022/04/13$)

問題《ゼッケンドルフの定理》

 $F_1 = F_2 = 1,$ $F_{n+2} = F_n+F_{n+1}$ で定まる数列 $\{ F_n\}$ を「フィボナッチ数列」と呼ぶ. すべての正の整数 $n$ に対して,
$[*]$
$n$ は「フィボナッチ数列」の隣り合わない項の和として表せる
が成り立つことを示せ. ただし,「フィボナッチ数列」の項そのものも項数が $1$ の和として考える.
(参考: $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$ は「フィボナッチ数列」の隣り合わない項の和として表せる.
したがって, $n = k$ のとき $[*]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[*]$ が成り立つ.

参考

  • すべての正の整数は「フィボナッチ数列」の隣り合わない項(第 $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$ 通りに表すこともできる(証明は同様).
(最終更新日: $2022/10/24$)

問題《$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}\] が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[*]$ が成り立つ.

参考

 円形に並んだ $n$ 人から $p$ 番隣の人を順に除いていくときに最後に残る人を決定する問題は「継子立て」または「ヨセフスの問題」(Josephus problem)と呼ばれる. 本問では最も簡単な $p = 2$ の場合を考えた.