個数に関する数学的帰納法と予選決勝法の関係

本記事の概要

多変量解析の手法として俗にいう「個数に関する数学的帰納法」と「予選決勝法」を取り上げ具体的な問題とその解説から両者の特徴や関係を分析することで、それらの書き方(型)への依存からの脱却を図ります。

問

2以上の整数nに対してn個の正の実数$x_i(i=1,2,3,...n)$について

この問題のポイント

変数の数が決まっていません。また、総和の条件が課されていますが、等式ではなく不等式です。

個数に関する数学的帰納法の問題として解く

$\displaystyle S_k=\sum_{i=1}^k x_i~(k=1,2,3,...n)$とする。

1. $n=2$のときを考える。

$S_2$を定数として$\displaystyle\sum_{i=1}^2 x_i(ix_i-1)$の最小値を求める。$x_2=S_2-x_1$より

この$n=2$の場合を考えることにより、$\displaystyle\frac{2}{3}(1+\log 2)^2-(1+\log 2)>0$

従って$\displaystyle S_2>1+\log 2>\frac{3}{4}$より$\displaystyle\frac{2}{3}S_2^2-S_2>\frac{2}{3}(1+\log 2)^2-(1+\log 2)$であり、結局$\displaystyle\sum_{i=1}^2 x_i(ix_i-1)>0$

1. ある2以上の整数$k$でn個の正の実数$x_i(i=1,2,3,...n)$について
   $\displaystyle\sum_{i=1}^k x_i \ge1+\log k$
   
   のとき
   $\displaystyle\sum_{i=1}^k x_i(ix_i-1)>0$
   ならば
   $\displaystyle\sum_{i=1}^{k+1} x_i \ge1+\log (k+1)$
   
   のとき
   $\displaystyle\sum_{i=1}^{k+1} x_i(ix_i-1)>0$
   を示す。ただし、「ならば」の前後で各$x_i$の値の一致不一致は考えないことに留意する。

数学的帰納法の型を組むことまではできたのですがそのままでは仮定のみをうまく使うのは難しいようです。(私が単に力不足だという可能性も捨てきれませんが。この記事をご覧になった方は是非この方針での解決お願いします。下に私の仮説を置いておきます。
$\displaystyle0<1+\log k<1+\log (k+1)-\frac{1}{k+1}<1+\log (k+1)$であり、「ならば」の後において
(1) $0<\displaystyle\sum_{i=1}^k x_i\le 1+\log k$のとき
(1) $1+\log k<\displaystyle\sum_{i=1}^k x_i$かつ$x_{k+1}>\displaystyle\frac{1}{k+1}$のとき
(1) $x_{k+1}\le\displaystyle\frac{1}{k+1}$のとき

として考えるとよい...?)

予選決勝法の問題として解く

$\displaystyle\sum_{i=1}^n x_i(ix_i-1)$の変数を$x_1,x_2,x_3,...$と順に動かし値を小さくします。総和の条件があるので最小値を$\displaystyle S_k=\sum_{i=1}^k x_i~(k=1,2,3,...n)$を用いて表すとよいでしょう。ただし、変数の数が決まっていないのでこちらでも数学的帰納法を使いました。

$\displaystyle S_k=\sum_{i=1}^k x_i~(k=1,2,3,...n)$とする。

1. $S_2$を定数として$\displaystyle\sum_{i=1}^2 x_i(ix_i-1)$の最小値を求める。$x_2=S_2-x_1$より

   \begin{eqnarray}\sum_{i=1}^2 x_i(ix_i-1) & = & x_1(x_1-1)+(S_2-x_1)\{2(S_2-x_1)-1\}\\ & = & 3\left(x_1-\frac{2}{3}S_2\right)^2+\frac{2}{3}S_2^2-S_2\end{eqnarray}
   
   $\displaystyle0\le \frac{2}{3}S_2\le S_2$より$\displaystyle\sum_{i=1}^2 x_i(ix_i-1)$の最小値は$\displaystyle\frac{2}{3}S_2^2-S_2\left(x_1=\frac{2}{3}S_2\right)$

2. &&&
   任意の2以上の整数nで正の実数$a_n$が存在し$\displaystyle\sum_{i=1}^n x_i(ix_i-1)$の最小値が$a_nS_n^2-S_n$である。

1. $1+\log n>0$
2. &&&
   任意の2以上の整数nで$\displaystyle\frac{1+\log n}{\displaystyle\sum_{k=1}^{n}\frac{1}{k}}-1>0$

1. 2の$a_n$について$\displaystyle a_2=\frac{2}{3},\frac{1}{a_{n+1}}=\frac{1}{a_{n}}+\frac{1}{n+1}$より$\displaystyle a_n=\frac{1}{\displaystyle\sum_{k=1}^{n} \frac{1}{k}}$だから、3,4より
   $\begin{eqnarray} a_nS_n^2-S_n & = & S_n\left(\frac{S_n}{\displaystyle\sum_{k=1}^{n} \frac{1}{k}}-1\right)\\ & \ge & (1+\log n)\left(\frac{1+\log n}{\displaystyle\sum_{k=1}^{n}\frac{1}{k}}-1\right)\\&>&0\end{eqnarray}$

以上より題意が示された。

見た目が似ているのでは?

(前半解決してないけど)書いてあることに同じところがありますね...(見える...!ない方針が見えるぞ...!)ここではこの問題の解説をもとに一般の類題における両者の違いを考えます。

どっちも変数の数が決まっていないおかげで数学的帰納法を使っています。しかしそもそも同じ手法を採用していながら前者は解決していないのでここに両者の関係の手がかりがあるのだろうと思います。私の経験によると両者を扱わせるよくある問題といえば下の表の通りで異なる特徴をもつと思います。

(ここでいう変数の独立とはある変数の値の組が1つに決定したとき他の変数の値の組がいわゆる有限の組み合わせに縛られないことを指す。)

一方で両者における解答の表現には対応しあう部分があります。それは変数の数を小さくして考える部分と徐々により多くの変数をひとまとめにして考える部分です。

この観点によると予選決勝法としての記述において
2以上の整数nに対してn個の正の実数$x_i(i=1,2,3,...n)$について

つまるところ、個数に関する数学的帰納法は仮定の設定に制限がある点で脆弱であり、予選決勝法はそれを補強するということです。私は一般に数学的帰納法を扱う問題に対して問題の内容をあまり工夫せずに使っていることにこの問題を通して気づかされました。