Binomial expansion

The binomial expansion states that num

(𝑥 + 𝑦) 𝑛 = 𝑛 \sum 𝑘 = 0 (𝑛 𝑘) 𝑥 𝑘 𝑦 𝑛 - 𝑘

where the so-called binomial coëfficients are given by

(𝑛 𝑘) = 𝑛! 𝑘! (𝑛 - 𝑘)! = 𝑛 C 𝑘

and $𝑛 C 𝑘$ is the number of ways to choose $𝑘$ elements of a set of size $𝑛$ . See also Generalized binomial coëfficient.

Proof

proof

Properties

(𝑛 𝑘) = (𝑛 𝑛 - 𝑘)

^P1 2.

𝑛 (𝑛 - 1 𝑛 - 1) = 𝑘 (𝑛 𝑘)

^P2 3.

(𝑚 + 𝑛 𝑘) = 𝑘 \sum 𝑗 = 0 (𝑚 𝑗) (𝑛 𝑘 - 𝑗)

^P3 4.

𝑛 \sum 𝑚 = 𝑘 (𝑛 𝑘) (𝑛 - 𝑚 𝑘 - 𝑗) = (𝑛 + 1 𝑘 + 1)

^P4 5.

𝑛 \sum 𝑚 = 𝑘 (𝑚 𝑘) = (𝑛 + 1 𝑘 + 1)

Proof of 1–3, 5

Clearly choosing $𝑘$ elements from a set of size $𝑛$ is the same as choosing $𝑛 - 𝑘$ elements to be excluded, proving ^P1.

Consider choosing a team of size $𝑘$ from a set of $𝑛$ people, where one member of the team is the captain. One can either first choose a captain and then the rest of the team (LHS), or the team and thence the captain (RHS), proving ^P2.

Consider a set of $𝑚$ red marbles and $𝑛$ blue marbles. The number of arbitrary choices of $𝑘$ marbles is the LHS, but this is the same as every possible way of choosing $𝑗$ red marbles and $𝑘 - 𝑗$ blue marbles (RHS). This proves ^P3.

A proof of ^P4 is missing, but ^P5 follows directly for $𝑗 = 𝑘$ .

Proof of 4

proof

develop | en | SemBr

Table of Contents

Binomial expansion

Properties

Graph View

Backlinks