Counting Principles - Main Theorem

The Binomial Theorem is the central result connecting combinatorics with algebra, providing a powerful tool for expanding powers and deriving identities involving binomial coefficients.

Proof (Combinatorial):

We provide a combinatorial proof by counting the terms in the expansion of $(x+y)^n = (x+y)(x+y)\cdots(x+y)$ ($n$ factors).

Each term in the expansion is obtained by choosing either $x$ or $y$ from each of the $n$ factors and multiplying these choices together. A term of the form $x^{n-k}y^k$ arises by choosing $y$ from exactly $k$ of the $n$ factors and $x$ from the remaining $n-k$ factors.

The number of ways to choose which $k$ factors contribute $y$ is $\binom{n}{k}$, since we are selecting $k$ positions from $n$ positions. Therefore, the coefficient of $x^{n-k}y^k$ is $\binom{n}{k}$.

Summing over all possible values of $k$ from 0 to $n$ gives: $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

Proof (Algebraic/Induction):

We prove by induction on $n$.

Base case: For $n=0$, $(x+y)^0 = 1 = \binom{0}{0}x^0y^0$, which is true.

Inductive step: Assume the formula holds for $n$. We show it holds for $n+1$: $(x+y)^{n+1} = (x+y)(x+y)^n = (x+y)\sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

Expanding: $= \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}$

Reindexing the second sum (replacing $k$ with $k-1$): $= \sum_{k=0}^{n} \binom{n}{k} x^{n+1-k} y^k + \sum_{k=1}^{n+1} \binom{n}{k-1} x^{n+1-k} y^k$

The $k=0$ term from the first sum is $\binom{n}{0}x^{n+1} = x^{n+1}$. The $k=n+1$ term from the second sum is $\binom{n}{n}y^{n+1} = y^{n+1}$. For $1 \leq k \leq n$, we use Pascal's identity: $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

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

This completes the induction. $\square$