binomial theorem

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

where $(\binom{n}{k})$ is the binomial coefficient, which appears in Pascal's triangle, and also in combinatorics as the combination or "choose function".

Proof

For $n = 0$ :

(x + y)^{0} = 1

(\binom{0}{0}) x^{0} y^{0} = 1 * 1 * 1 = 1

Suppose that the theorem holds for $n$ ;

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

It suffices to show the case $n + 1$ necessarily holds.

\begin{aligned} P_{n + 1} : (x + y)^{n + 1} & = (x + y)^{1} \cdot (x + y)^{n} \\ = (x + y) \cdot \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} \\ = x \cdot \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} + y \cdot \sum_{t = 0}^{m} (\binom{m}{t}) x^{m - t} y^{t} \\ = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k + 1} y^{k} + \sum_{t = 0}^{m} (\binom{m}{t}) x^{m - t} y^{t + 1} \end{aligned}

Terms combine when $n - k + 1 = m - t$ and $k = t + 1$ .
Then $m = t - k + n + 1 = (- 1) + n + 1 = n$ ,
and we can write

= \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}

\begin{aligned} = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) x^{n + 1 - k} y^{k} \end{aligned}

So by the principle of mathematical induction, the theorem holds for all $n \in N$ .

QED.