logo

Binomial Theorem Proof 📂Lemmas

Binomial Theorem Proof

Definition

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

Theorem

Binomial Theorem

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

Pascal’s Identity

(nk)+(nk+1)=(n+1k+1) \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}

Binomial Coefficient Sum Formula

2n=k=0n(nk) 2^{n} = \sum_{k=0}^{n} \binom{n}{k}

Binomial Coefficient Subtraction Formula

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

Binomial Coefficient Squared Sum Formula

(2nn)=k=0n(nk)2 \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(x+y)^{n}, the coefficients of xkynkx^{k} y^{n-k} are the same as selecting xx from each (x+y)(x+y), with nn chosen, and yy chosen nrn-r times. Therefore, the combination count nCr_n C _r becomes the coefficient of xkynkx^{k} y^{n-k}, so the following holds true. (x+y)n=k=0nnCkxkynk (x+y)^{n} = \sum_{k=0}^{n} {_n C _k} x^{k} y^{n-k}