📂Lemmas

Binomial Theorem Proof

Definition

1. A combination is a subset of a finite set.
2. The number of subsets with cardinality $k$ from a set with cardinality $n$ is denoted by $\binom{n}{k}$ or $_{n}C_{k}$, and is called the binomial coefficient. $$\binom{n}{k} = _{n}C_{k} = \frac{ n! }{ k! (n-k)! }$$

Theorem

Binomial Theorem

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

Pascal’s Identity

$$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$

Binomial Coefficient Sum Formula

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

Binomial Coefficient Subtraction Formula

$$\binom{n}{k} \left( {\frac{ n }{ k }} \right)^{-1} = \binom{n-1}{k-1}$$

Binomial Coefficient Squared Sum Formula

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

Explanation

Note that, except for the Binomial Theorem, the names of the other formulas are not the actual commonly used names, but arbitrary ones created for convenience.

The Binomial Theorem is the most famous and important theorem in combinatorics and is widely applied across various fields.

Proof

The proofs other than the Binomial Theorem are discussed in detail in the respective documents for each formula.

---

When expanding $(x+y)^{n}$, the coefficients of $x^{k} y^{n-k}$ are the same as selecting $x$ from each $(x+y)$, with $n$ chosen, and $y$ chosen $n-r$ times. Therefore, the combination count $_n C _r$ becomes the coefficient of $x^{k} y^{n-k}$, so the following holds true. $$(x+y)^{n} = \sum_{k=0}^{n} {_n C _k} x^{k} y^{n-k}$$

■