数学I / 集合と命題

調和数は整数にならない

最難関編背理法偶奇の論証

問題

$n$ を2以上の整数とするとき、 $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ は整数でないことを示せ。

ヒントを見る

分母たちの中で「2で割れる回数」に注目する。いちばん多く2で割れる数は、 $n$ 以下にいくつあるか — もし2つあったら間に何が挟まるはずか。その「ただ1つ」の項だけが、通分の世界で仲間はずれになる。

解答・解説

方針

n 以下の整数のうち、2で割れる回数が最大のもの(2^m)はただ1つ。これが急所だ。和に「2^{m−1}×(1〜n の奇数の積)」を掛けると、1/2^m の項だけが半整数になり、他の項はすべて整数になる。整数+非整数は非整数なので、和は整数になり得ない。

解答

⓪ 発想 — どう考え始めるか。 通分して分子を調べたいが、分母の最小公倍数は複雑だ。そこで、2で割れる回数(2のべき)だけに注目する。

$n$ 以下で最大の2のべきを $2^{m}$ とすると、 $2^{m}$ は $n$ 以下でただ1つ。 $2^{m}$ の2倍 $2^{m + 1}$ はもう $n$ を超えるし、 $2^{m}$ の奇数倍 $3 \cdot 2^{m}$ はさらに大きいからだ。

この「仲間はずれの1項」 $\frac{1}{2 ^{m}}$ が急所になる。うまく選んだ数を掛けると、この項だけが整数にならない。背理法はそこで決まる。

重要

n

以下で2で割れる回数が最大の数

2^{m}

はただ1つ(

3 \cdot 2^{m} > 2^{m + 1} > n

)。「整数の和+整数でない1項」は整数でない

① 仲間はずれを特定する。 $2^{m} \leq n < 2^{m + 1}$ となる $m \geq 1$ をとる( $n \geq 2$ なので存在)。 $k \leq n$ で $k \neq = 2^{m}$ なら、 $k$ の2で割れる回数は $m - 1$ 以下である。もし $m$ 回以上割れたら、 $k$ は $2^{m}$ の倍数。 $k \neq = 2^{m}$ なら $k \geq 2 \cdot 2^{m} = 2^{m + 1} > n$ となって矛盾する。

② 掛けて整数性を仕分ける。 $Q$ を $1$ から $n$ までの奇数すべての積とし、 $L = 2^{m - 1} Q$ を和に掛ける。 $k \neq = 2^{m}$ の項は、 $k = 2^{e} \cdot (奇数)$ ( $e \leq m - 1$ )と書けるから

$\frac{L}{k} = \frac{2 ^{m - 1} Q}{2 ^{e} \cdot ( 奇数 )} = 2^{m - 1 - e} \cdot \frac{Q}{( 奇数 )}$

は整数だ( $Q$ はその奇数を因数にもつ)。一方、 $k = 2^{m}$ の項は

$\frac{L}{2 ^{m}} = \frac{Q}{2}$

で、 $Q$ は奇数だから整数でない。

③ 背理法で締める。 和 $H = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ が整数と仮定すると、 $L H$ は整数のはず。だが②より $L H = (整数の和) + \frac{Q}{2}$ で、整数でない。矛盾。よって $H$ は整数でない。

まとめ: 「最大の2のべきはただ1つ」という一点が、証明の全体重を支えている。素朴に通分するのではなく、うまい倍率 $L$ を設計して1項だけを仲間はずれにする。発想の芯は、集合の中の「唯一の極端な要素」に目をつけることだ。

発展 — 一歩先へ。 同じ論法を磨くと、もっと強いことが言える。 $n \geq 2$ の $H$ は「約分し尽くすと分母が偶数」の分数になる。さらに、 $\frac{1}{m} + \frac{1}{m + 1} + \dots + \frac{1}{n}$ (項が2つ以上の連続区間の和)も、すべて整数にならない。「区間内で2で割れる回数が最大の数はただ1つ」が、そのまま通用するからだ。

答

証明( $n$ 以下で最大の2のべき $2^{m}$ がただ1つであることを使う背理法)

別解

最小公倍数で一気に通分する(定番の別ルート)。 掛ける数を自分で設計する代わりに、 $1$ から $n$ の最小公倍数 $L$ で普通に通分してもよい。

$H = \frac{\frac{L}{1} + \frac{L}{2} + \dots + \frac{L}{n}}{L}$

$L$ の素因数2の個数はちょうど $m$ ( $n$ 以下の最大の2のべき $2^{m}$ から来る)。すると各分子 $\frac{L}{k}$ のうち、奇数になるのは $k = 2^{m}$ の項ただ1つで、他はすべて偶数だ( $k$ の2の個数が $m$ 未満なら、 $\frac{L}{k}$ に2が残る)。

分子の総和は「奇数1個+偶数たち」で奇数。分母 $L$ は偶数( $m \geq 1$ )。奇数を偶数で割っても、2は約分できないから整数にならない。

掛け算 $L$ を設計する本解と、最小公倍数で通分する本ルート。どちらも心臓部は同じ「 $2^{m}$ の唯一性」で、装いだけが違う。分子の偶奇という1ビットに情報を圧縮するのが、この証明の見どころだ。

ポイント

$n$ 以下の最大の2のべき $2^{m}$ は唯一。
$L = 2^{m - 1} \times (奇数の積)$ を掛けると $\frac{1}{2 ^{m}}$ の項だけ $\frac{Q}{2}$ (非整数)。
整数の和+非整数 → 全体は非整数(背理法)。

よくある間違い

小さい $n$ で実験して「整数にならなそう」で終える。実験は予想であって、すべての $n$ の証明にはならない。
「最大の2のべき」が2つ以上あると思ってしまう。 $2^{m}$ の次に2で $m$ 回割れる数は $2 \cdot 2^{m} = 2^{m + 1}$ で、もう $n$ を超えている。
掛ける数 $L = 2^{m - 1} \times (奇数の積)$ を天下りに出す。「全項を整数化したいが、 $\frac{1}{2 ^{m}}$ だけはわざと半端に残す」という設計意図を一言添える。