Mathematical induction proves a statement for every integer in a consecutive range. The base case starts the chain, and the induction step shows that each true case forces the next one.

The induction principle

Let $P(n)$ be a proposition defined for every integer $n\ge n_0$. To prove that all of these propositions are true:

1. Base case: prove $P(n_0)$.
2. Induction hypothesis: let $n\ge n_0$ be arbitrary and temporarily assume $P(n)$.
3. Induction step: use that assumption to prove $P(n+1)$.
4. Conclude that $P(n)$ holds for every integer $n\ge n_0$.

The induction step proves the implication $P(n)\Rightarrow P(n+1)$ for an arbitrary allowed $n$. It does not assume the whole theorem. Together with the base case, it creates the chain

$$P(n_0) \Rightarrow P(n_0+1) \Rightarrow P(n_0+2) \Rightarrow\cdots.$$

This forward scheme covers a natural-number range such as $n\ge n_0$. One base case and one forward step do not automatically cover all integers, rationals, or real numbers.

Example: the sum of the first $n$ positive integers

We will prove

$$1+2+\cdots+n=\frac{n(n+1)}2 \qquad(n\ge1).$$

Base case. At $n=1$,

$$1=\frac{1(1+1)}2.$$

Induction hypothesis. Let $n\ge1$ and assume

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

Induction step. Add the next integer and use the hypothesis on the part already known:

$$\begin{aligned} 1+2+\cdots+n+(n+1) &=\frac{n(n+1)}2+(n+1)\\ &=\frac{n(n+1)+2(n+1)}2\\ &=\frac{(n+1)(n+2)}2\\ &=\frac{(n+1)((n+1)+1)}2. \end{aligned}$$

This is exactly $P(n+1)$. Therefore the formula holds for every integer $n\ge1$.

Example: when an exponential outruns a line

We will prove

$$2n+1<2^n \qquad(n\ge3).$$

The starting index matters: the inequality fails at $n=0,1,2$.

Base case. At $n=3$,

$$2(3)+1=7<8=2^3.$$

Induction hypothesis. Let $n\ge3$ and assume $2n+1<2^n$.

Induction step. Then

$$\begin{aligned} 2(n+1)+1 &=(2n+1)+2\\ &<2^n+2 &&\text{by the induction hypothesis}\\ &<2^n+2^n &&\text{because }2<2^n\text{ for }n\ge3\\ &=2^{n+1}. \end{aligned}$$

So the inequality holds for every integer $n\ge3$.

Pascal's triangle and the binomial pattern

The coefficients in the first few powers of $x+y$ form the rows of Pascal's triangle:

$$\begin{aligned} (x+y)^1&=x+y,\\ (x+y)^2&=x^2+2xy+y^2,\\ (x+y)^3&=x^3+3x^2y+3xy^2+y^3,\\ (x+y)^4&=x^4+4x^3y+6x^2y^2+4xy^3+y^4. \end{aligned}$$

The coefficient rows are

$$\begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1. \end{array}$$

Each interior entry is the sum of the two above it. This is Pascal's identity:

$$\binom nk+\binom n{k-1}=\binom{n+1}k \qquad(1\le k\le n).$$

One way to prove it is to count the $k$-element subsets of an $(n+1)$-element set. Fix one special element. A subset either excludes it, giving $\binom nk$ choices, or includes it and chooses the remaining $k-1$ elements from the other $n$, giving $\binom n{k-1}$ choices.

The binomial theorem

For every nonnegative integer $n$,

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

The term with index $k$ contains $k$ copies of $y$ and $n-k$ copies of $x$. Its coefficient is $\binom nk$ because we choose which $k$ of the $n$ factors contribute $y$.

Example: extracting one coefficient

In

$$(2x+y)^{25} =\sum_{k=0}^{25}\binom{25}{k}(2x)^{25-k}y^k,$$

the term containing $y^{13}$ has $k=13$. Its $x$-power is $25-13=12$:

$$\binom{25}{13}(2x)^{12}y^{13} =\binom{25}{13}2^{12}x^{12}y^{13}.$$

Therefore the coefficient of $x^{12}y^{13}$ is

$$\boxed{\binom{25}{13}2^{12}}.$$

Proof of the binomial theorem by induction

Let $P(n)$ be the displayed binomial identity.

Base case. For $n=0$, both sides are the constant polynomial $1$:

$$(x+y)^0=1 =\binom00x^0y^0.$$

Induction hypothesis. Assume for some $n\ge0$ that

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

Induction step. Multiply by $x+y$ and use the hypothesis:

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

For an interior exponent $1\le k\le n$, the monomial $x^{n+1-k}y^k$ comes from both sums. Its coefficient is

$$\binom nk+\binom n{k-1}=\binom{n+1}k.$$

The endpoints have only one source. When $k=0$, the first sum contributes $x^{n+1}$. When $k=n+1$, the second contributes $y^{n+1}$. Since

$$\binom{n+1}{0}=\binom{n+1}{n+1}=1,$$

we obtain

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

Thus $P(n+1)$ follows, so the theorem holds for every $n\ge0$.

Why a row sums to $2^n$

For every $n\ge0$,

$$\boxed{\sum_{k=0}^{n}\binom nk=2^n}.$$

There are two useful proofs.

Count subsets by size. An $n$-element set has $2^n$ subsets because each element is either included or excluded. It has $\binom nk$ subsets of size $k$. The size classes $k=0,1,\ldots,n$ are disjoint and include every subset, so their counts add to $2^n$.

Use the binomial theorem. Set $x=y=1$:

$$2^n=(1+1)^n =\sum_{k=0}^{n}\binom nk1^{n-k}1^k =\sum_{k=0}^{n}\binom nk.$$

The endpoint $n=0$ also works: the empty set has exactly one subset, itself.