11. Proofs by induction

Proofs by induction

To prove a property $P(n)$ is true for all positive integers $n$, we:

• Basis step: Prove that $P(1)$ is true.
• Inductive step: Prove that the conditional statement $P(k)\to P(k+1)$ is true for all positive integers $k$.

To complete the inductive step of a proof by induction,

• assume that $P(k)$ is true for an arbitrary positive integer $k$
• show that under this assumption, $P(k+1)$ must also be true

The inductive hypothesis (IH) is the assumption that $P(k)$ is true.

Example

Show that for every positive integer, $n$, that $1+2+...+n=\frac{n(n+1)}{2}$.

• Basis step: $P(1)$ is true, because $1=\frac{1(1+1)}{2}$.
• Inductive step: For the inductive hypothesis, we assume that $P(k)$ holds for an arbitrary positive integer $k$. $$1+2+...+k=\frac{k(k+1)}{2}\text{ (IH)}$$

$$Underthisassumption:$$

\begin{aligned} \boxed{1 + 2 + … + (k + 1)} &= (1 + 2 + … + k) + (k + 1) \ &\stackrel{\textsf{by IH}}{=} \frac{k(k+1)}{2} + (k + 1) \ &= \frac{k(k + 1) + 2(k + 1)}{2} \ &= \frac{(k + 2)(k + 1)}{2} \ &= \boxed{ \frac{ (k + 1)((k + 1) + 1) }{2} } \end{aligned}