Let $P(i)$ be a statement for $i = 1, 2, 3, \dots.$ A proof by induction is helpful when you want to prove $$\bigcap_{i=1}^\infty P(i)$$ In other words, you want to prove that the statements $P(i)$ are simultaneously true for all numbers $i.$

$\bigcap_{i=1}^\infty$

A proof by induction is a proof using the following strategy:

• Base case: Prove $P(1).$
• Inductive step: Prove $P(i) \rightarrow P(i+1)$ for $i \geq 1.$ In the proof of the inductive step, $P(i)$ is called the inductive hypothesis.

Once the base case and inductive step are proved, then the statements $P(i)$ are proved for $i = 1, 2, 3, \dots.$ This is because $P(1)$ was proved, and since $P(i) \rightarrow P(i+1)$ was proved, $P(1) \rightarrow P(2)$ implies $P(2)$ is a tautology (since $P(1)$ is a tautology). Since $P(2)$ is a tautology and $P(2) \rightarrow P(3),$ $P(3)$ is a tautology. Proceeding this way, the truth of all of the statements follows.

Example

Claim: For $i \geq 1,$ $$\sum_{j=1}^i j = \frac{i(i+1)}{2}$$

$\sum_{j=1}^i$

Proof: When doing a proof by induction, it is good to state what strategy you are using to avoid confusing the reader. This will be a proof by induction.

Base case: First let $i = 1.$ The sum is $$\sum_{j=1}^1 j = 1$$ The fraction is $$\frac{1 \cdot (1+1)}{2} = 1$$
Inductive step: Assume that for some number $n \geq 1,$ $$\sum_{j=1}^n j = \frac{n(n+1)}{2}$$ We need to show the claim for $n+1.$ When we plug in $n+1,$ the claim becomes $$\sum_{j=1}^{n+1} j = \frac{(n+1)(n+2)}{2}$$ First, rewrite the sum. Then use the inductive hypothesis. $$\begin{align} \sum_{j=1}^{n+1} j & = \left( \sum_{j=1}^n j \right) + (n+1) \\ & = \frac{n(n+1)}{2} + (n+1) \end{align}$$ By getting a common denominator and combining like terms, one can show $$\frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$$ which proves the claim.