Combinationの性質: 二項定理の応用

Problem

$1$より大きい奇数 $n$ が任意に与えられている. このとき,

$\\_nC_1, \\_nC_2, \cdots, \\_nC_{\frac{n-1}{2}}$

のなかに奇数は奇数個存在することを示せ.

証明

二項定理より

\[\begin{align*} (1 + 1)^n &= _nC_0 + _nC_1 + _nC_2 + \cdots + _nC_{\frac{n-1}{2}} + _nC_{\frac{n+1}{2}} + \cdots + _nC_{n-1} + _nC_n\\ &= 2^n \end{align*}\]

従って,

\[\begin{align*} _nC_1 + _nC_2 + \cdots + _nC_{\frac{n-1}{2}} &= \frac{1}{2}(2^n - 2)\\ &= 2^{n-1} - 1\\ &= \text{奇数} \end{align*}\]

従って, $(\\_nC_1, \\_nC_2, \cdots, \\_nC_{(n-1)/2})$ の中に奇数は奇数個存在する.

証明終了

References

数学オリンピックへの道 1 組合せ論の精選102問

Share Buttons
Share on:

Feature Tags
Leave a Comment
(注意：GitHub Accountが必要となります）

Combinationの性質: 二項定理の応用

組合せ論シリーズ 1/N

References

CONTENTS