問題 15

問題015｜整数・二項係数

難易度 D 目安 60

前半戦

整数 $a, b, c, d$ が $c + d \neq 0$ を満たすとする．このとき，分数 $\frac{a + b}{c + d}$ が既約分数であるための十分条件は $a d - b c = 1$ であることを示せ．

$n$ を正の整数， $x$ を実数とする．次の和を求めよ．

(\binom{n}{1}) \cos x + (\binom{n}{2}) \cos 2 x + \dots + (\binom{n}{n}) \cos n x

後半戦

$a, b$ を正の整数とする．このとき，次の関係を示せ．ただし， $u ∣ v$ は整数 $u$ が整数 $v$ を割り切ることを表す．

gcd (2^{a} + 1, 2^{b} + 1) ∣ 2^{gcd (a, b)} + 1

正の数 $b_{1}, b_{2}, \dots, b_{m}$ の幾何平均とは，それらの積の正の $m$ 乗根 $(b_{1} b_{2} \dots b_{m})^{1 / m}$ のことである．正の整数 $n$ に対して，二項係数 $(\binom{n}{0}), (\binom{n}{1}), \dots, (\binom{n}{n})$ の幾何平均を

G_{n} = {(\prod_{r = 0}^{n} (\binom{n}{r}))}^{1 / (n + 1)}

とする．このとき，

lim_{n \to \infty} \sqrt[n]{G_{n}} = \sqrt{e}

を証明せよ．

ヒント設問 1

ヒント 1

$a + b$ と $c + d$ の公約数は，それらの整数倍の差も割り切る．

ヒント 2

$d (a + b) - b (c + d)$ を計算する．

ヒント設問 2

ヒント 1

正弦を用いた和も合わせて考え，オイラーの公式と二項定理を使う．

ヒント 2

$1 + e^{i x} = 2 \cos (x / 2) e^{i x / 2}$ と変形した後，実部を比較する．

ヒント設問 3

ヒント 1

$d = gcd (a, b)$ ， $D = gcd (2^{a} + 1, 2^{b} + 1)$ とおく．

ヒント 2

13日目の結果から $D ∣ 2^{2 d} - 1$ を示す．次に $D$ と $2^{d} - 1$ が互いに素であることを確認する．

ヒント設問 4

ヒント 1

二項係数の積を階乗で表し， $1! 2! \dots n!$ の中に各整数 $j$ が何回現れるかを数える．

ヒント 2

積の各因子の指数の和が $0$ であることを使って底を $j / (n + 1)$ に直し，対数を取る．端点で発散する対数の項は，積分との大小比較で扱う．

解答設問 1

$a d - b c = 1$ と仮定する． $a + b$ と $c + d$ の正の公約数を $g$ とすると， $g$ はそれらの整数倍の差

d (a + b) - b (c + d) = a d - b c = 1

も割り切る．したがって $g = 1$ であり，分子と分母は互いに素である． $c + d \neq 0$ なので分数は定義され， $\frac{a + b}{c + d}$ は既約分数となる．よって， $a d - b c = 1$ は十分条件である．

解答設問 2

求める和を $S$ とし，

T = \sum_{k = 1}^{n} (\binom{n}{k}) \sin k x

とおく． $i$ を虚数単位とすると，オイラーの公式 $e^{i θ} = \cos θ + i \sin θ$ より，

\begin{aligned} 1 + S + i T & = \sum_{k = 0}^{n} (\binom{n}{k}) (\cos k x + i \sin k x) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) (e^{i x})^{k} \\ = (1 + e^{i x})^{n} \end{aligned}

となる．ここで，左辺に加えた $1$ は $k = 0$ の項に対応し，最後の等式には二項定理を用いた．

さらに，

\begin{aligned} 1 + e^{i x} & = e^{i x / 2} (e^{- i x / 2} + e^{i x / 2}) \\ = 2 \cos \frac{x}{2} e^{i x / 2} \end{aligned}

と変形できるので，

\begin{aligned} 1 + S + i T & = {(2 \cos \frac{x}{2})}^{n} e^{i n x / 2} \\ = 2^{n} \cos^{n} \frac{x}{2} (\cos \frac{n x}{2} + i \sin \frac{n x}{2}) \end{aligned}

を得る．両辺の実部を比較して $1$ を引くと，求める和は

S = 2^{n} \cos^{n} \frac{x}{2} \cos \frac{n x}{2} - 1

である．

解答設問 3

d = gcd (a, b), D = gcd (2^{a} + 1, 2^{b} + 1)

とおく． $D$ は $2^{a} + 1$ と $2^{b} + 1$ を割り切るので，

2^{2 a} - 1 = (2^{a} - 1) (2^{a} + 1), 2^{2 b} - 1 = (2^{b} - 1) (2^{b} + 1)

も割り切る．13日目に示した等式 $gcd (n^{r} - 1, n^{s} - 1) = n^{gcd (r, s)} - 1$ を用いると，

gcd (2^{2 a} - 1, 2^{2 b} - 1) = 2^{gcd (2 a, 2 b)} - 1 = 2^{2 d} - 1

であるから，

D ∣ (2^{d} - 1) (2^{d} + 1)

を得る．

ここで， $D$ と $2^{d} - 1$ が互いに素であることを示す． $d ∣ a$ より， $a = d m$ と正の整数 $m$ を用いて表せるので，

2^{a} - 1 = (2^{d} - 1) (1 + 2^{d} + \dots + 2^{(m - 1) d})

となる．したがって， $D$ と $2^{d} - 1$ の正の公約数 $g$ は， $2^{a} + 1$ と $2^{a} - 1$ をともに割り切り，その差 $2$ も割り切る．一方， $g$ は奇数 $2^{d} - 1$ の約数なので奇数であり， $g = 1$ でなければならない．よって， $gcd (D, 2^{d} - 1) = 1$ である．

互いに素な整数についての割り切りの性質より， $D ∣ (2^{d} - 1) (2^{d} + 1)$ から $D ∣ 2^{d} + 1$ が従う．したがって，

gcd (2^{a} + 1, 2^{b} + 1) ∣ 2^{gcd (a, b)} + 1

が成り立つ．

解答設問 4

二項係数の積を整理する

A_{n} = \prod_{r = 0}^{n} (\binom{n}{r})

とおく．幾何平均は $n + 1$ 個の数について取るので， $G_{n} = A_{n}^{1 / (n + 1)}$ である．二項係数を階乗で表すと，

\begin{aligned} A_{n} & = \prod_{r = 0}^{n} \frac{n!}{r! (n - r)!} \\ = \frac{(n!)^{n + 1}}{(\prod_{r = 0}^{n} r!) (\prod_{r = 0}^{n} (n - r)!)} \\ = \frac{(n!)^{n + 1}}{(1! 2! \dots n!)^{2}} \end{aligned}

となる．最後の等式では， $n - r$ も $0, 1, \dots, n$ を一度ずつ取り， $0! = 1$ であることを用いた．

ここで， $1! 2! \dots n!$ に含まれる各整数の個数を数える．整数 $j$ は， $j!, (j + 1)!, \dots, n!$ のそれぞれに一度ずつ現れるので，全部で $n + 1 - j$ 回現れる．したがって，

1! 2! \dots n! = \prod_{j = 1}^{n} j^{n + 1 - j}

である．一方，分子 $(n!)^{n + 1}$ では各 $j$ が $n + 1$ 回現れる．よって，分子と分母の指数の差を取ると，

\begin{aligned} A_{n} & = \prod_{j = 1}^{n} j^{(n + 1) - 2 (n + 1 - j)} \\ = \prod_{j = 1}^{n} j^{2 j - n - 1} \end{aligned}

を得る．指数が負となる因子は，分母に残ることを意味する．

さらに，これらの指数の和は，

\sum_{j = 1}^{n} (2 j - n - 1) = 2 \frac{n (n + 1)}{2} - n (n + 1) = 0

である．したがって，各因子の底を $n + 1$ で割っても，積全体には $(n + 1)^{0} = 1$ しか掛からず，

A_{n} = \prod_{j = 1}^{n} {(\frac{j}{n + 1})}^{2 j - n - 1}

と表せる．両辺の $1 / (n + 1)$ 乗を取ると，

G_{n} = \prod_{j = 1}^{n} {(\frac{j}{n + 1})}^{2 j / (n + 1) - 1}

となる．対数を取り，極限を求める

以下， $\log$ は自然対数とする． $N = n + 1$ とおくと，

\begin{aligned} \log \sqrt[n]{G_{n}} & = \frac{1}{n} \log G_{n} \\ = \frac{N}{n} {\frac{2}{N} \sum_{j = 1}^{N - 1} \frac{j}{N} \log \frac{j}{N} - \frac{1}{N} \sum_{j = 1}^{N - 1} \log \frac{j}{N}} \end{aligned}

となる．中括弧内の二つの和をそれぞれ調べる．

まず， $t \log t$ は $t \to 0 +$ のとき $0$ に収束するので， $t = 0$ での値を $0$ と定めれば $[0, 1]$ 上で連続となる．したがって，区分求積法により，

lim_{N \to \infty} \frac{1}{N} \sum_{j = 1}^{N - 1} \frac{j}{N} \log \frac{j}{N} = \int_{0}^{1} t \log t d t = - \frac{1}{4}

である．積分値は，部分積分で得られる原始関数 $\frac{t^{2}}{2} \log t - \frac{t^{2}}{4}$ と， $lim_{t \to 0 +} t^{2} \log t = 0$ から求まる．

次に， $\log t$ は $t = 0$ で発散するため，通常の連続関数の区分求積法をそのまま適用することはできない．そこで， $\log t$ が単調増加することを用いる．各区間で積分と長方形の面積を比較すると，

\int_{0}^{(N - 1) / N} \log t d t \leq \frac{1}{N} \sum_{j = 1}^{N - 1} \log \frac{j}{N} \leq \int_{1 / N}^{1} \log t d t

となる． $\int \log t d t = t \log t - t$ と $lim_{t \to 0 +} t \log t = 0$ より，左右の積分はいずれも $\int_{0}^{1} \log t d t = - 1$ に収束する．したがって，はさみうちの原理から，

lim_{N \to \infty} \frac{1}{N} \sum_{j = 1}^{N - 1} \log \frac{j}{N} = - 1

を得る．

以上と $N / n = (n + 1) / n \to 1$ より，

lim_{n \to \infty} \log \sqrt[n]{G_{n}} = 2 (- \frac{1}{4}) - (- 1) = \frac{1}{2}

となる．指数関数の連続性を用いれば，

lim_{n \to \infty} \sqrt[n]{G_{n}} = e^{1 / 2} = \sqrt{e}

が従う．

DISCUSSION

この問題の掲示板

この掲示板は公開されています。ニックネームと本文は、ログインしていない人にも表示されます。Googleアカウントの名前は表示されません。

閲覧はどなたでもできます。ログインすると投稿できます。

まだ投稿はありません。