이항 정리 (Binomial Theorem) 은 다음과 같습니다.
$$ {(x + y)}^{n} = \sum_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k} = {x}^{n} + n {x}^{n - 1} y+\frac{n (n - 1)}2 x^{n - 2} y^{2} + \cdots + y^{n} $$$\binom{n}{k}$는 이항계수 입니다.
$n = 0$인 경우에는 $\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k} = \sum\limits_{k = 0}^{0} \binom{0}{k} {x}^{-k} {y}^{k} = \binom{0}{0} {x}^{0} {y}^{0} = 1$이고, 좌변도 ${(x + y)}^{n} = {(x + y)}^{0} = 1$로, 좌변과 우변이 동일하다.
$\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k}$ 식에서 $k = 0$일 때만 따져본다면, 즉, $$ \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 0}^{0} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} + \sum\limits_{k = 1}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} $$ 으로 분리한다면 $\binom{n}{0} {x}^{n + 1 - 0} {y}^{0} = x^{n + 1}$이므로, $\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} = x^{n + 1} + \sum\limits_{k = 1}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k}$ 로 쓸 수 있다.
$\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k + 1}$ 식에서 편의상 $K = k + 1$로 치환 하면 $\sum\limits_{K = 1}^{n + 1} \binom{n}{K - 1} {x}^{n + 1 - K} {y}^{K}$ 이 되고, 다시 $k = K$로 써주면 $\sum\limits_{k = 1}^{n + 1} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k}$ 이다.
$n = 1$인 경우에는 $\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k} = \sum\limits_{k = 0}^{1} \binom{1}{k} {x}^{1 - k} {y}^{k} = \binom{1}{0} {x}^{1} {y}^{0} + \binom{1}{1} {x}^{0} {y}^{1} = x + y$이고, 좌변도 ${(x + y)}^{n} = {(x + y)}^{1} = x + y$로, 좌변과 우변이 동일하다.
이제 어떤 $n$에 대해 ${(x + y)}^{n} = \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k}$이 성립한다고 가정하면, 먼저 ${(x + y)}^{n + 1} = (x + y) {(x + y)}^{n} = (x + y) \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k}$이다.
$(x + y) \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k}$를 식정리 해주면 $\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} + \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k + 1}$이다.
$\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k}$ 식 정리
$\sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k + 1}$ 식 정리
$\sum\limits_{k = 1}^{n + 1} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k}$ 식을 $k = n + 1$일 때의 항만 따지면 $\binom{n}{n} {x}^{0} {y}^{n + 1} = y^{n + 1}$로 쓸 수 있다. 따라서 $\sum\limits_{k = 1}^{n + 1} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k} = y^{n + 1} + \sum\limits_{k = 1}^{n} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k}$ 로 분리해서 쓸 수 있다.
$\sum\limits_{k = 1}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} + \sum\limits_{k = 1}^{n} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 1}^{n} \left\{ \binom{n}{k} + \binom{n}{k - 1} \right\} {x}^{n + 1 - k} {y}^{k}$이라 할 수 있다.
이항계수의 항등식에서 $\binom{n}{k}+\binom{n}{k - 1} = \binom{n + 1}{k}$이므로, $\sum\limits_{k = 1}^{n} \left\{ \binom{n}{k} + \binom{n}{k - 1} \right\} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 1}^{n} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$이다.
$\binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$ 식에 $k = 0$을 대입하면 $\binom{n + 1}{0} {x}^{n + 1 - 0} {y}^{0} = x^{n + 1}$이므로, $x^{n + 1} + \sum\limits_{k = 1}^{n} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 0}^{n} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$ 이라 할 수 있다.
$\binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$ 식에 $k = n + 1$을 대입하면 $\binom{n + 1}{n + 1} {x}^{n + 1 - (n + 1)} {y}^{n + 1} = y^{n + 1}$이므로, $y^{n + 1} + \sum\limits_{k = 0}^{n} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 0}^{n + 1} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$ 이라 할 수 있다.
따라서 $x^{n + 1} + y^{n + 1} + \sum\limits_{k = 1}^{n} \binom{n}{k} {x}^{n + 1 - k} {y}^{k} + \sum\limits_{k = 1}^{n} \binom{n}{k - 1} {x}^{n + 1 - k} {y}^{k} = \sum\limits_{k = 0}^{n + 1} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$이다.
따라서 ${(x + y)}^{n + 1} = \sum\limits_{k = 0}^{n + 1} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$이다.
어떤 $n$에 대해서 ${(x + y)}^{n} = \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k}$이 성립할 때 ${(x + y)}^{n + 1} = \sum\limits_{k = 0}^{n + 1} \binom{n + 1}{k} {x}^{n + 1 - k} {y}^{k}$이 성립하므로, 수학적 귀납법 에 의해 ${(x + y)}^{n} = \sum\limits_{k = 0}^{n} \binom{n}{k} {x}^{n - k} {y}^{k}$ 는 $0$ 이상의 정수 전체에서 성립한다.
$$ \sum_{k = 0}^{n} \binom{n}{k} = 2^{n} $$$x = y = 1$로 두면 쉽게 이를 얻을 수 있습니다.