이항정리

먼저 귀납 단계에 쓸 파스칼 항등식 $\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$ ($1 \leq k \leq n$)를 확인합니다. 정의 $\binom{n}{k}=\frac{n!}{k!(n-k)!}$를 대입하면 $\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}$이고, $\frac{n!}{(k-1)!(n-k)!}$로 묶어내면 $\frac{n!}{(k-1)!(n-k)!}\left(\frac1k+\frac1{n-k+1}\right) = \frac{n!}{(k-1)!(n-k)!}\cdot\frac{n+1}{k(n-k+1)} = \frac{(n+1)!}{k!(n+1-k)!} = \binom{n+1}{k}$입니다.

기저 $n = 0$: 여기서 $0^0 = 1$이라는 관례를 씁니다 (빈 곱, empty product) — $x + y = 0$이어도 $(x+y)^0 = 1$이고, $x = 0$ 또는 $y = 0$이어도 $x^0, y^0$ 항은 $1$입니다. 좌변은 $(x+y)^0 = 1$이고, 우변은 $k=0$인 항 하나뿐이라 $\binom{0}{0}x^0y^0 = 1\cdot 1\cdot 1 = 1$ — 성립합니다.

$n$에서 성립한다고 가정합니다. $(x+y)^{n+1} = (x+y)(x+y)^n$에 귀납 가설을 대입하면 $\sum_{k=0}^{n}\binom{n}{k}x^{n+1-k}y^k + \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k+1}$을 얻습니다.

두 번째 합에서 $j = k+1$로 치환하면 $\sum_{j=1}^{n+1}\binom{n}{j-1}x^{n+1-j}y^j$가 됩니다 (첫 번째 합의 $k$도 $j$로 다시 씁니다).

$1 \leq j \leq n$에서 $x^{n+1-j}y^j$의 계수는 $\binom{n}{j}+\binom{n}{j-1}$이며, 파스칼 항등식으로 $\binom{n+1}{j}$가 됩니다.

경계항은 $j=0$에서 $\binom{n}{0} = 1 = \binom{n+1}{0}$, $j=n+1$에서 $\binom{n}{n} = 1 = \binom{n+1}{n+1}$이므로 전체 합은 $\sum_{j=0}^{n+1}\binom{n+1}{j}x^{n+1-j}y^j$ — 정확히 $n+1$에서의 공식입니다.

기저와 귀납 단계로 모든 $n \geq 0$에서 이항정리가 성립합니다. 핵심은 파스칼 항등식입니다 — 이항계수의 점화식이 $(x+y)$를 한 번 더 곱하는 귀납 단계와 정확히 맞아떨어집니다.

이항정리에 $x = 1$, $y = 1$을 대입합니다. 좌변은 $(1+1)^n = 2^n$이 됩니다.

우변은 $\sum_{k=0}^{n}\binom{n}{k}1^{n-k}1^k = \sum_{k=0}^{n}\binom{n}{k}$입니다 ($1$의 거듭제곱은 $1$). 따라서 $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ — 파스칼 삼각형의 각 행의 합이 $2$의 거듭제곱이 되는 이유입니다.

이항정리에 $x = 1$, $y = -1$을 대입합니다. 좌변은 $(1+(-1))^n = 0^n$인데, $n \geq 1$이므로 $0^n = 0$입니다 ($n = 0$은 $0^0$이 관례상 $1$이므로 제외합니다).

우변은 $\sum_{k=0}^{n}\binom{n}{k}1^{n-k}(-1)^k = \sum_{k=0}^{n}(-1)^k\binom{n}{k}$입니다. 따라서 $\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0$ — 파스칼 삼각형의 각 행에 부호를 번갈아 붙이면 합이 $0$이 됩니다.