数学B 数学的帰納法 問題 12 解説

方針・初手

中央二項係数

$$ {}_{2n}C_n={}_{2n}\mathrm{C}_{n} $$

を、積の形と二項定理の両方から評価する。下からは積表示で各因子が $2$ 以上であることを使い、上からは二項展開のすべての係数の和が $4^n$ であることを使う。

解法1

まず、二項係数を積の形で表すと、

$$ \begin{aligned} {}_{2n}\mathrm{C}_{n} &= \frac{(2n)!}{n!n!} \\ \frac{(n+1)(n+2)\cdots(2n)}{1\cdot 2\cdots n} \\ \prod_{k=1}^{n}\frac{n+k}{k} \end{aligned} $$

である。

ここで、$1\leqq k\leqq n$ より $n\geqq k$ であるから、

$$ n+k\geqq 2k $$

が成り立つ。したがって、

$$ \frac{n+k}{k}\geqq 2 $$

である。これを $k=1,2,\ldots,n$ について掛け合わせると、

$$ \begin{aligned} {}_{2n}\mathrm{C}_{n} &= \prod_{k=1}^{n}\frac{n+k}{k} \geqq \prod_{k=1}^{n}2 &= 2^n \end{aligned} $$

となる。よって、

$$ 2^n\leqq {}_{2n}\mathrm{C}_{n} $$

が示された。

次に、二項定理より、

$$ \begin{aligned} (1+1)^{2n} &= \sum_{k=0}^{2n}{}_{2n}\mathrm{C}_{k} \end{aligned} $$

である。左辺は

$$ (1+1)^{2n}=2^{2n}=4^n $$

であるから、

$$ \begin{aligned} 4^n &= \sum_{k=0}^{2n}{}_{2n}\mathrm{C}_{k} \end{aligned} $$

である。

各二項係数 ${}_{2n}\mathrm{C}_{k}$ は正であり、${}_{2n}\mathrm{C}_{n}$ はその和の中の1項である。したがって、

$$ \begin{aligned} {}_{2n}\mathrm{C}_{n} \leqq \sum_{k=0}^{2n}{}_{2n}\mathrm{C}_{k} &= 4^n \end{aligned} $$

となる。

以上より、

$$ 2^n\leqq {}_{2n}\mathrm{C}_{n}\leqq 4^n $$

が成り立つ。

解法2

数学的帰納法で示すこともできる。

$$ a_n={}_{2n}\mathrm{C}_{n} $$

とおく。

まず $n=1$ のとき、

$$ a_1={}_{2}\mathrm{C}_{1}=2 $$

であるから、

$$ 2^1\leqq a_1\leqq 4^1 $$

が成り立つ。

次に、$a_n$ と $a_{n+1}$ の比を調べる。

$$ \begin{aligned} \frac{a_{n+1}}{a_n} &= \frac{{}_{2n+2}\mathrm{C}_{n+1}}{{}_{2n}\mathrm{C}_{n}} \\ \frac{(2n+2)(2n+1)}{(n+1)^2} \\ \frac{2(2n+1)}{n+1} \end{aligned} $$

である。

ここで $n\geqq 1$ のとき、

$$ 2\leqq \frac{2(2n+1)}{n+1}\leqq 4 $$

が成り立つ。実際、左側は

$$ \frac{2(2n+1)}{n+1}\geqq 2 \iff 2n+1\geqq n+1 \iff n\geqq 0 $$

であり、右側は

$$ \frac{2(2n+1)}{n+1}\leqq 4 \iff 2n+1\leqq 2n+2 $$

であるから、ともに成り立つ。

したがって、

$$ 2a_n\leqq a_{n+1}\leqq 4a_n $$

である。

帰納法の仮定として

$$ 2^n\leqq a_n\leqq 4^n $$

が成り立つとする。このとき、

$$ a_{n+1}\geqq 2a_n\geqq 2\cdot 2^n=2^{n+1} $$

であり、また

$$ a_{n+1}\leqq 4a_n\leqq 4\cdot 4^n=4^{n+1} $$

である。

よって、

$$ 2^{n+1}\leqq a_{n+1}\leqq 4^{n+1} $$

が成り立つ。

以上より、数学的帰納法によって、すべての自然数 $n$ について

$$ 2^n\leqq {}_{2n}\mathrm{C}_{n}\leqq 4^n $$

が成り立つ。

解説

下限 $2^n$ は、中央二項係数を

$$ \begin{aligned} {}_{2n}\mathrm{C}_{n} &= \prod_{k=1}^{n}\frac{n+k}{k} \end{aligned} $$

と見て、各因子が $2$ 以上であることから得られる。

上限 $4^n$ は、二項定理

$$ \sum_{k=0}^{2n}{}_{2n}\mathrm{C}_{k}=4^n $$

において、${}_{2n}\mathrm{C}_{n}$ がその和の中の1項であることから得られる。

この問題では、${}_{2n}\mathrm{C}_{n}$ を単に計算するのではなく、「積表示で下から評価する」「二項係数の和で上から評価する」という2つの見方を使い分けることが重要である。

答え

すべての自然数 $n$ について、

$$ 2^n\leqq {}_{2n}C_n\leqq 4^n $$

が成り立つ。