📂Lemmas

Binomial Theorem Proof

Definition

1. A combination of a finite set is a subset.
2. The number of subsets with a cardinality $r$ from a set with a cardinality of $n$ is expressed as ${_n C _r}$ and is called the binomial coefficient. $${_n C _r} = \binom{n}{r} = {{ n! } \over { r ! (n-r)! }}$$

Theorem

Binomial Theorem

$$(x+y)^{n} = \sum_{r=0}^{n} {_n C _r} x^{r} y^{n-r}$$

Binomial Coefficient Subtraction Formula

$$\binom{m}{x} \left( {\frac{ m }{ x }} \right)^{-1} = \binom{m-1}{x-1}$$

Explanation

Note that the names of the formulas, except for the Binomial Theorem, are not actually used in practice but have been arbitrarily assigned for ease of use.

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

Proof

Proofs for the formulas other than the Binomial Theorem are addressed separately in each respective document.

---

When expanding $(x+y)^{n}$, the coefficient of $x^{r} y^{n-r}$ is equivalent to choosing $x$ $n$ times and $y$ $n-r$ times from each $(x+y)$ of $$(x+y)^{n} = (x+y)(x+y)(x+y) \cdots (x+y)$$. Therefore, the number of combinations $_n C _r$ becomes the coefficient of $x^{r} y^{n-r}$, resulting in: $$(x+y)^{n} = \sum_{r=0}^{n} {_n C _r} x^{r} y^{n-r}$$

■