数学の命題示しました

主に組合せ論について，読んだ本で出てきたことや，考えたことを書きます．

2021-05-29

n人から偶数人を選ぶ方法は2^{n-1}通り

命題

自然数 $n$ に対して以下が成立する．
$\displaystyle\sum_{k\geq 0}\binom{n}{2k}=2^{n-1}$ .

証明

$n$ 人の中から偶数人の参加者を選ぶ方法が $2^{n-1}$ 通りであることを言えばよい．
参加者を次のように決める：
一人目，二人目,..., $n-1$ 人目までは，参加／不参加を自由に決める．
最後の $n$ 人目は参加者の合計が偶数になるように，それまでの選び方に依存して決める．
よって，決め方は $2^{n-1}$ 通り．
（証明終わり）

補足

ここから， $n$ 人から奇数人を選ぶ方法も $2^{n-1}$ 通りであることがわかる．