TheoremProved

Binomial theorem

Statement

For any nonnegative integer $n$ , $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$ , where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ .

Why is it true?

Expanding $(x+y)^n$ means choosing, for each of the $n$ factors, whether to take $x$ or $y$ ; the coefficient of $x^{n-k}y^k$ counts the number of ways to choose which $k$ of the $n$ factors contribute a $y$ , which is exactly $\binom{n}{k}$ .

Proof sketch

By induction on $n$ using Pascal's identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ : write $(x+y)^n = (x+y)(x+y)^{n-1}$ , expand $(x+y)^{n-1}$ by the inductive hypothesis, distribute $x$ and $y$ over each term, and collect the coefficient of $x^{n-k}y^k$ from the two contributions, which combine via Pascal's identity to give $\binom{n}{k}$ .

Proved by

proved 1654Blaise Pascal

Topics that use this theorem

The binomial theorem

Related theorems

Pigeonhole principle

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science