以下の2つの等式を証明し、組み合わせの意味に基づいて説明します。 1. $\sum_{k=0}^{n} {n \choose k} = 2^n$

1. 問題の内容

以下の2つの等式を証明し、組み合わせの意味に基づいて説明します。

1. $\sum_{k=0}^{n} {n \choose k} = 2^n$

2. $\sum_{k=0}^{n} {n \choose k}^2 = {2n \choose n}$

2. 解き方の手順

1. $\sum_{k=0}^{n} {n \choose k} = 2^n$の証明

* 二項定理を使用する方法:

二項定理とは、任意の非負整数 $n$ に対して、

$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k$

が成り立つというものです。ここで、$x = 1, y = 1$ とすると、

$(1+1)^n = \sum_{k=0}^{n} {n \choose k} 1^{n-k} 1^k$

$2^n = \sum_{k=0}^{n} {n \choose k}$

* 組み合わせの意味:

$n$個の要素からなる集合の部分集合の総数を考えます。各要素に対して、「部分集合に含める」か「含めない」かの2通りの選択肢があるため、部分集合の総数は $2^n$ です。

一方、部分集合の要素数が $k$ 個であるような部分集合の数は ${n \choose k}$ です。したがって、要素数 $0$ から $n$ までのすべての部分集合の数を合計すると、$\sum_{k=0}^{n} {n \choose k}$ となります。

これら2つの考え方は同じものを数えているので、$\sum_{k=0}^{n} {n \choose k} = 2^n$ が成り立ちます。

2. $\sum_{k=0}^{n} {n \choose k}^2 = {2n \choose n}$の証明

* 組み合わせの意味:

$2n$ 人の中から $n$ 人を選ぶ組み合わせの数 ${2n \choose n}$ を考えます。

$2n$ 人を $n$ 人ずつの2つのグループAとBに分けます。$2n$ 人から $n$ 人を選ぶことは、グループAから $k$ 人選び、グループBから $n-k$ 人選ぶことと同じです。ここで、$k$ は $0$ から $n$ までの整数を取りえます。

グループAから $k$ 人を選ぶ組み合わせの数は ${n \choose k}$ であり、グループBから $n-k$ 人を選ぶ組み合わせの数は ${n \choose n-k}$ です。組み合わせの数を計算する際、$n \choose k$ = $n \choose n-k$ を使用することができます。そのため、$\sum_{k=0}^{n} {n \choose k} {n \choose n-k} = \sum_{k=0}^{n} {n \choose k} {n \choose k} = \sum_{k=0}^{n} {n \choose k}^2$ となります。

したがって、${2n \choose n} = \sum_{k=0}^{n} {n \choose k}^2$ が成り立ちます。

3. 最終的な答え

1. $\sum_{k=0}^{n} {n \choose k} = 2^n$

2. $\sum_{k=0}^{n} {n \choose k}^2 = {2n \choose n}$