調和数

1・2：$H_k=\sum_{j\le k}\frac1j$ を代入して $j$ と $k$ の和の順序を入れかえる。$j$ を固定すると $k$ は $j$ から $n$ まで動くので
$$ \sum_{k=1}^nH_k=\sum_{j=1}^n\frac{n-j+1}j=(n+1)H_n-n, $$
$$ \sum_{k=1}^nkH_k=\sum_{j=1}^n\frac1j\sum_{k=j}^nk=\sum_{j=1}^n\frac1j\Bigl(\frac{n(n+1)}2-\frac{j(j-1)}2\Bigr)=\frac{n(n+1)}2H_n-\frac12\sum_{j=1}^n(j-1) $$
であり、$\sum_{j=1}^n(j-1)=\frac{n(n-1)}2$ である。
3：$x\ne1$ で $\frac{1-x^n}{1-x}=\sum_{k=0}^{n-1}x^k$ であり、$\int_0^1x^k\,dx=\frac1{k+1}$ なので、積分は $\sum_{k=0}^{n-1}\frac1{k+1}=H_n$ である。
4：3 で $x=1-y$ と置き換えると $H_n=\int_0^1\frac{1-(1-y)^n}y\,dy$ である。二項定理から $1-(1-y)^n=\sum_{k=1}^n(-1)^{k-1}\binom nky^k$ なので、被積分関数は $\sum_{k=1}^n(-1)^{k-1}\binom nky^{k-1}$ であり、項ごとに積分して 4 を得る。$\square$

$1\le H_n\le n$ なので、左辺の冪級数は $|x|< 1$ で絶対収束する。その和を $G(x)$ とおくと、$H_0=0$ と $H_n-H_{n-1}=\frac1n$ から
$$ (1-x)G(x)=\sum_{n\ge1}H_nx^n-\sum_{n\ge1}H_{n-1}x^n=\sum_{n\ge1}(H_n-H_{n-1})x^n=\sum_{n\ge1}\frac{x^n}n $$
である（2 つの級数はどちらも絶対収束するので、項ごとに引いてよい）。関数の近似とテイラー展開 の定理「対数関数の展開」を $-x$ に使うと、$|x|< 1$ で $\sum_{n\ge1}\frac{x^n}n=-\log(1-x)=\log\frac1{1-x}$ である。$1-x$ で割って主張を得る。$\square$

$k\ge1$ とする。$k< x< k+1$ で $\frac1{k+1}< \frac1x< \frac1k$ なので、連続関数を積分して
$$ \frac1{k+1}< \int_k^{k+1}\frac{dx}x=\log(k+1)-\log k< \frac1k $$
である（対数関数 の定理「積分による表示」）。右の不等号を $k=1,\dots,n$ について加えると $\log(n+1)< H_n$ である。$n\ge2$ なら、左の不等号を $k=1,\dots,n-1$ について加えると $H_n-1< \log n$ である。$n=1$ では $H_1=1=1+\log1$ である。$\square$

thm-hn-log から $D_n>\log(n+1)-\log n>0$ である。prf-hn-log の評価から
$$ D_n-D_{n+1}=\bigl(\log(n+1)-\log n\bigr)-\frac1{n+1} $$
は $0$ より大きく、$\frac1n-\frac1{n+1}$ より小さい。よって $(D_n)$ は下に有界な狭義単調減少列で、極限 $\gamma\ge0$ をもつ（単調収束定理）。$e_k:=D_k-D_{k+1}$、$d_k:=\frac1k-\frac1{k+1}$ とおくと $0< e_k< d_k$ であり、$N\to\infty$ とした望遠鏡和から
$$ D_n-\gamma=\sum_{k=n}^\infty e_k,\qquad\frac1n=\sum_{k=n}^\infty d_k $$
である。各 $e_k$ は正なので $D_n-\gamma>0$ であり、$\frac1n-(D_n-\gamma)=\sum_{k\ge n}(d_k-e_k)\ge d_n-e_n>0$ なので $D_n-\gamma< \frac1n$ である。$\square$

右辺の和は、$H_{2n}$ から偶数番目の項を 2 回引いたものなので、$H_{2n}-2\sum_{j=1}^n\frac1{2j}=H_{2n}-H_n$ である。また $H_{2n}-H_n=\log2+D_{2n}-D_n$ であり、thm-hn-gamma から $D_{2n}< D_n$、$D_n-D_{2n}< D_n-\gamma< \frac1n$ なので、評価を得る。$\square$

整数 $k\ge1$ が $2$ で割り切れる回数を $v(k)$ と書き（$k=2^{v(k)}\cdot(\text{奇数})$）、$s:=\max_{m\le k\le n}v(k)$ とおく。$m< n$ なので範囲には連続する 2 つの整数があり、その一方は偶数だから $s\ge1$ である。
段 1（最大の項はただ 1 つ）。範囲の中に $2^s$ の倍数が 2 つ、$u2^s< w2^s$ があるとすると、$u< u+1\le w$ より $(u+1)2^s$ も範囲にある。$u$ と $u+1$ の一方は偶数なので、$u2^s$ と $(u+1)2^s$ の一方は $2^{s+1}$ で割り切れ、$s$ の最大性に反する。よって $v(k)=s$ となる $k$ はただ 1 つで、それを $k_0$ とする。
段 2（偶奇を比べる）。$L$ を $m,m+1,\dots,n$ の最小公倍数とすると、$L$ が $2$ で割り切れる回数は $s$ である。$k\ne k_0$ なら $v(k)< s$ なので $L/k$ は偶数であり、$L/k_0$ は奇数である。したがって
$$ L\sum_{k=m}^n\frac1k=\sum_{k=m}^n\frac Lk $$
は奇数である。和 $\sum_{k=m}^n\frac1k$ が整数なら、左辺は偶数 $L$（$s\ge1$）の倍数なので偶数になり、矛盾する。$\square$

$k$ と $p-k$ を組にすると
$$ 2H_{p-1}=\sum_{k=1}^{p-1}\Bigl(\frac1k+\frac1{p-k}\Bigr)=p\sum_{k=1}^{p-1}\frac1{k(p-k)} $$
である。右の和を通分すると分母を $B:=((p-1)!)^2$ にとれるので、整数 $A$ を使って $H_{p-1}=\frac{pA}{2B}$ と書ける。$p$ は奇数で $(p-1)!$ の因数はどれも $p$ より小さいので、$2B$ は $p$ で割り切れない。$\frac ND=\frac{pA}{2B}$ から $2BN=pAD$ であり、$p$ は素数で $2B$ を割り切らないので $p\mid N$ である。$\square$

$k$ 個の元からなる部分集合 $A$ を固定する。$A$ がちょうど $\sigma$ の 1 つの巡回をなす置換 $\sigma$ は、$A$ の元を 1 つの巡回に並べる方法 $(k-1)!$ 通りと、補集合の置換 $(n-k)!$ 通りを組み合わせて得られる。よって、$\sigma$ と、$\sigma$ の長さ $k$ の巡回の台 $A$ の組の個数は $\binom nk(k-1)!(n-k)!=\frac{n!}k$ である。$n!$ で割ると、長さ $k$ の巡回の個数の期待値は $\frac1k$ である。巡回の個数は長さごとの個数の和なので、期待値 の定理「期待値の線形性」から、その期待値は $\sum_{k=1}^n\frac1k=H_n$ である。$\square$