1

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

738
0
$$$$

本記事の概要

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

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

$\displaystyle\sum_{i=1}^n x_i \ge1+\log n$

のとき
$\displaystyle\sum_{i=1}^n x_i(ix_i-1)>0$
を示せ。

この問題のポイント

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

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

$\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$より

\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)$
また、
(1) $1+\log n>0$
(1)
&&&
$\displaystyle\frac{(1+\log n)}{\displaystyle\sum_{k=1}^{n}\frac{1}{k}}-1>0$

&&&prf
kを1以上の整数として$k\le x< k+1$$\displaystyle\frac{1}{x}> \frac{1}{k+1}$だから

$\begin{eqnarray}\int_{k}^{k+1}\frac{1}{x}dx&>&\int_{k}^{k+1}\frac{1}{k+1}dx \\\sum_{k=1}^{n-1}\int_{k}^{k+1}\frac{1}{x}dx&>&\sum_{k=1}^{n-1}\int_{k}^{k+1}\frac{1}{k+1}dx\\\int_{1}^{n}\frac{1}{x}dx&>&\sum_{k=1}^{n-1}\frac{1}{k+1}\\\log n&>&\displaystyle\sum_{k=1}^{n}\frac{1}{k}-1\end{eqnarray}$
$\displaystyle\sum_{k=1}^{n}\frac{1}{k}>0$より上が従う。

この$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$である。

&&&prf
$S_n$を定数としてある2以上の整数$k$で正の実数$a_k$が存在し$\displaystyle\sum_{i=1}^k x_i(ix_i-1)$の最小値が$a_kS_k^2-S_k$であるならば正の実数$a_{k+1}$が存在し$\displaystyle\sum_{i=1}^{k+1} x_i(ix_i-1)$の最小値は$a_{k+1}S_{k+1}^2-S_{k+1}$であることを示す。

\begin{eqnarray}\sum_{i=1}^{k+1} x_i(ix_i-1)&=&\displaystyle\sum_{i=1}^k x_i(ix_i-1)+x_{k+1}\{(k+1)x_{k+1}-1\}\\&\ge& (a_kS_k^2-S_k)+(S_{k+1}-S_k)\{(k+1)(S_{k+1}-S_k)-1\}\\ & = & (a_k+k+1)\left(S_k-\frac{k+1}{a_k+k+1}S_{k+1}\right)^2+\frac{a_k(k+1)}{a_k+k+1}S_{k+1}^2-S_{k+1}\end{eqnarray}

上の式の不等号は$S_k$によらずある正の実数の組$(x_1,x_2,x_3,...x_k)$で等号が成立する。また、$\displaystyle0\le\frac{k+1}{a_k+k+1}S_{k+1}\le S_{k+1}$だから$\displaystyle\sum_{i=1}^{k+1} x_i(ix_i-1)$の最小値は$\displaystyle\frac{k+1}{a_k+k+1}S_{k+1}^2-S_{k+1}$であり、$\displaystyle a_{k+1}=\frac{a_k(k+1)}{a_k+k+1}>0$である。
よって1を踏まえることで上が示された。

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

&&&prf 再掲
kを1以上の整数として$k\le x< k+1$$\displaystyle\frac{1}{x}> \frac{1}{k+1}$だから

$\begin{eqnarray}\int_{k}^{k+1}\frac{1}{x}dx&>&\int_{k}^{k+1}\frac{1}{k+1}dx \\\sum_{k=1}^{n-1}\int_{k}^{k+1}\frac{1}{x}dx&>&\sum_{k=1}^{n-1}\int_{k}^{k+1}\frac{1}{k+1}dx\\\int_{1}^{n}\frac{1}{x}dx&>&\sum_{k=1}^{n-1}\frac{1}{k+1}\\\log n&>&\displaystyle\sum_{k=1}^{n}\frac{1}{k}-1\end{eqnarray}$
$\displaystyle\sum_{k=1}^{n}\frac{1}{k}>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)$について

$\displaystyle\sum_{i=1}^n x_i(ix_i-1)\ge\frac{\displaystyle\sum_{i=1}^n x_i}{\displaystyle\sum_{k=1}^{n} \frac{1}{k}}-\displaystyle\sum_{i=1}^n x_i$
であることを示した部分が個数に関する数学的帰納法においても同じくそれを示す過程にあたります。しかし本問では総和の条件及びそれに伴う簡潔な結果が追加されているために問題全体に対して数学的帰納法を適用すると活用するのに難解な仮定になるようです。

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

投稿日:202158

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

記事の方針 ・一般に「上手い」とされている操作を取り上げ、考える者の能力と照らし合わせその理由を解き明かす。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中