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.