How Do You Write a Proof by Mathematical Induction?

A proof by mathematical induction has four required stages: verify a base case, assume the statement is true for $n=k$, prove it for $n=k+1$, and state the conclusion. This is IB Mathematics: Analysis and Approaches HL, sub-topic AHL 1.15, and the method applies on any paper where induction is examined.

Induction works like a chain of dominoes. The base case establishes the first statement. The inductive step then proves that whenever one permitted statement is true, the next statement must also be true. These two facts establish every statement in the specified integer domain; induction does not prove a claim merely by checking several examples.

The Induction Structure

Suppose the proposition to be proved is called $P(n)$.

1. Base case: Verify $P(n)$ for the first permitted value, usually $n=1$.
2. Inductive hypothesis: Assume $P(k)$ is true for some permitted integer $k$.
3. Inductive step: Using that assumption, demonstrate that $$ must also be true.

Worked Example

Prove that the sum of the first $n$ positive odd integers is $n^2$:

$$1+3+5+\cdots +(2n-1)=n^2.$$

Base case: When $n=1$,

$$1=1^2,$$

so $P(1)$ is true.

Inductive hypothesis: Assume $P(k)$ is true for some $k\in\mathbb{Z}^{+}$. Thus,

$$1+3+\cdots +(2k-1)=k^2.$$

Inductive step: The next odd integer is $2(k+1)-1=2k+1$. Therefore,

$$1+3+\cdots +(2k-1)+(2k+1) =k^2+2k+1 =(k+1)^2.$$

The crucial point is that $k^2$ replaces the earlier sum because the inductive hypothesis has explicitly assumed that equality.

Hence, if $P(k)$ is true, then $P(k+1)$ is true.

Conclusion: Since $P(1)$ is true and $P(k)\Rightarrow P(k+1)$, the statement is true for all $n\in\mathbb{Z}^{+}$ by mathematical induction.

Exam Technique

For the command term prove, every logical stage must appear. A common misconception is writing “let $n=k$” instead of explicitly assuming that $P(k)$ is true; this does not establish the inductive hypothesis. Examiners also expect the final induction conclusion, not merely the algebra for $k+1$. Do not assume the result for $k+1$; derive it from the hypothesis for .