📂보조정리

이항계수 합 공식

공식

이항계수 합 공식 ¹

이항계수의 합은 다음과 같다. $$ 2^{n} = \sum_{k=0}^{n} \binom{n}{k} $$

따름정리: 멱집합의 기수

유한집합 $S$ 의 기수가 $n = |S|$ 이면 그 멱집합 $2^{S}$ 의 기수는 $2^{n}$ 이다.

유도

이항정리: $$ (x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k} $$

$x = y = 1$ 을 대입하면 $2^{n} = \sum_{k=0}^{n} \binom{n}{k} 1^{k} 1^{n-k}$ 을 얻는다.

■