Nhị thức Newton

Khai triển $(a+b)(a+b)\cdots(a+b)$ ($n$ nhân tử) nghĩa là chọn $a$ hoặc $b$ từ mỗi nhân tử rồi nhân lại; hệ số của $a^{n-k}b^k$ chính là số cách chọn $b$ từ $k$ trong $n$ nhân tử, tức là $\binom{n}{k}$.

Chứng minh bằng quy nạp theo $n$. Cơ sở $n=1$: $(a+b)^1=a+b=\binom{1}{0}a+\binom{1}{1}b$, khớp với công thức vì $\binom{1}{0}=\binom{1}{1}=1$.

Bước quy nạp: giả sử công thức đúng với một $n$ nào đó, tức $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$. Nhân hai vế với $(a+b)$: $(a+b)^{n+1}=\sum_{k=0}^n\binom{n}{k}a^{n+1-k}b^k+\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}$.

Đổi chỉ số của tổng thứ hai với $j=k+1$ rồi gộp hệ số của $a^{n+1-j}b^j$ từ hai tổng, ta được $\binom{n}{j}+\binom{n}{j-1}$ với mỗi $j$ từ $0$ đến $n+1$ (quy ước $\binom{n}{-1}=\binom{n}{n+1}=0$).

Theo quy tắc Pascal $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$, tổng này bằng $\binom{n+1}{j}$, nên $(a+b)^{n+1}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{n+1-j}b^j$, hoàn tất quy nạp.

Đặt $a$ và $b$ đều bằng $1$ trong định lý nhị thức, mỗi số hạng $a^{n-k}b^k$ trở thành $1$, nên toàn bộ tổng chỉ còn là số lượng số hạng.

Thay $a=1,\ b=1$ vào định lý nhị thức $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$: vế trái trở thành $(1+1)^n=2^n$, vế phải trở thành $\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k=\sum_{k=0}^n\binom{n}{k}$, vì $1$ lũy thừa bất kỳ vẫn bằng $1$.

Cho hai vế bằng nhau, ta được đúng $2^n=\sum_{k=0}^n\binom{n}{k}$.

Đẳng thức này còn có ý nghĩa tổ hợp trực tiếp: $\binom{n}{k}$ đếm các tập con gồm $k$ phần tử của một tập $n$ phần tử $S$, nên $\sum_{k=0}^n\binom{n}{k}$ đếm mọi tập con của $S$ với kích thước bất kỳ, tức toàn bộ tập lũy thừa, có đúng $2^n$ phần tử vì mỗi phần tử trong $n$ phần tử độc lập thuộc hoặc không thuộc một tập con.