Proof of the Complex Binomial Formula

This is a presentation of the proof for the binomial formula for complex numbers. The intent is to provide a clear example of an inductive proof.

Theorem

Let $z_1, z_2 \in \mathbb C$ and $n \in \mathbb N$. Then

\[(z_1 + z_2)^n = \sum_{k=0}^n \binom{n}{k}z_1^k z_2^{n-k}\]

Proof

By induction on $n$.

Base Case: ( $n = 1$)

\[\begin{aligned} \sum_{k = 0}^1 \binom{1}{k} z_1^k z_2^{1 - k} &\stackrel{?}{=} (z_1 + z_2)^1\\ \underbrace{\binom{1}{0} z_1^0 z_2^{1-0}}_{k = 0} + \underbrace{\binom{1}{1} z_1^1 z_2^{1 - 1}}_{k = 1} &\stackrel{?}{=} z_1 + z_2\\ 1 \cdot 1 \cdot z_2 + z \cdot z_1 \cdot 1 &\stackrel{?}{=} z_1 + z_2\\ z_2 + z_1 &\stackrel{\checkmark}{=} z_1 + z_2\\ \end{aligned}\]

Thus the base case holds.

Assume the statement is true for $n$, we wish to show that the statement is true for $n + 1$.

Consider $(z_1 + z_2)^{n + 1}$, we wish to show that $\displaystyle{(z_1 + z_2)^{n + 1} = \sum_{k = 0}^{n + 1} \binom{n + 1}{k}z_1^k z_2^{n + 1 - k}}$.

\[(z_1 + z_2)^{n + 1} = (z_1 + z_2) \cdot (z_1 + z_2)^n\]

\[(z_1 + z_2)^{n + 1} = (z_1 + z_2) \cdot \left(\sum_{k = 0}^n \binom{n}{k} z_1^k z_2^{n - k}\right)\]

Multiplying $(z_1 + z_2)$ through the sum we get

\[\sum_{k = 0}^n \binom{n}{k} z_1 ^{k + 1} z_2^{n - k} + \sum_{k = 0}^n \binom{n}{k} z_1^k z_2^{n + 1 - k}\]

We reindex the first summation $k \to j - 1$. Note that $k = j - 1$ and $ k + 1 = j$.

\[\sum_{j = 1}^{n + 1} \binom{n}{j - 1} z_1^j z_2^{n + 1 - j} + \sum_{k = 0}^n \binom{n}{k} z_1^k z_2^{n + 1 - k}\]

We split off the first term of the last summation and the last term of the first summation.

\[\underbrace{\binom{n}{n} z_1^{n + 1} z_2^0}_{j = n+1} + \sum_{k = 1}^n \left[\binom{n}{k - 1} + \binom{n}{k}\right] z_1^k z_2^{n + 1 - k} + \underbrace{\binom{n}{0} z_1^0 z_2^{n + 1}}_{k = 0}\]

Note that $\binom{n}{k - 1} + \binom{n}{k} = \binom{n + 1}{k}$. This is proved as a lemma later. We then have

\[1 \cdot z^{n + 1} \cdot z_2^0 + \sum_{k = 1}^n \binom{n + 1}{k} z_1^k z_2^{n + 1 - k} + 1 \cdot z_1^0 \cdot z_2^{n + 1}\]

Noting that $\binom{n}{n} = 1$ and $\binom{n}{0} = 1$ we have

\[\underbrace{\binom{n + 1}{n + 1} \cdot z^{n + 1} \cdot z_2^0}_{\text{$k = n+1$ term}} + \sum_{k = 1}^n \binom{n + 1}{k} z_1^k z_2^{n + 1 - k} + \underbrace{\binom{n + 1}{0} \cdot z_1^0 \cdot z_2^{n + 1}}_{\text{$k = 0$ term}}\]

We then have the following

\[\sum_{k = 0}^{n + 1} \binom{n + 1}{k}z_1^k z_2^{n + 1 - k}\]

Which is precisely what we wanted to show $(z_1 + z_2)^{n + 1}$ is equal to. Therefore, the statement is true for $n + 1$ and thus for all $n$.

Lemma

\[{\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}}\]

Proof

Label one of the $n + 1$ objects as $*$. We can either choose $*$ as one of our $k$ objects or not. These are two distinct and disjoint cases, and are all that are possible.

If we choose $*$, we are left to choose $k - 1$ objects from $n$ objects. This can be done in $\binom{n}{k - 1}$ ways.
If we don't choose $*$, then we are left to choose $k$ objects from $n$ objects. This can be done $\binom{n}{k}$ ways.

Therefore, we have $\displaystyle{\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}}$.

Note this lemma could be proved using the definition of $\displaystyle\binom{n}{k} = \frac{n!}{k!(n - k!)}$, but that would require more algebra than is pleasant. Also note that this proof of the binomial formula for complex numbers exemplifies the three parts of an induction proof:

It's also a good idea in proof-writing to be extremely clear both in what proof method you're using and which part of the proof you're currently working on.

Proof of the Complex Binomial Formula — an inductive proof