As you journey into higher-level mathematics, you will gain a better appreciation for the significance of proofs. Proving what is claimed to be true is fundamental to the nature of mathematics, a system built on logic. Proof by induction, also known as the Principle of Mathematical Induction, is a popular method that is used to prove the veracity of a proposition.

The Idea

Suppose that we wanted to formally prove a proposition, $P(n)$, to be true $\mathrm{\forall }n\in \mathbb{N}$.

Of course, we can directly substitute $n=1$, $n=2$, and so on to prove the proposition for these values of $n$. However, our aim is to prove the proposition for all natural numbers. Directly substituting every single natural number in existence is simply impossible as there are infinitely many. Therefore, we must consider proof by induction in this scenario.

Step 1: Defining $P(n)$

Writing the proposition every single time you need to refer to it can be extremely tedious. Thus, it is recommended to represent the proposition symbolically. Also, it is good practice to formally define what $P(n)$ means before using it.

For example, if you are tasked with showing that $$\sum _{r=1}^{n}r=\frac{n(n+1)}{2}$$ for all whole numbers, you should write $$\text{Let }P(n)\text{ be the proposition that }\sum _{r=1}^{n}r=\frac{n(n+1)}{2}\mathrm{\forall }n\in W.$$

Note: $P(n)$ is just notation to represent a proposition. It is not a function.

Step 2: The Base Case

Firstly, we must find the minimum value of $n$ for which $P(n)$ is true. You should consider how $n$ was defined in this context to determine this value.

• If $n\in \mathbb{N}$ or $n\in {\mathbb{Z}}^{+}$, then the minimum value of $n$ is $1$.
• If $n\in \mathbb{W}$, then the minimum value of $n$ is $0$.
• Sometimes, a question may specify that $n>2$. In this scenario, the minimum value of $n$ is $3$.

Once we have determined the minimum value of $n$, we need to directly substitute the value into the proposition to manually verify that it is true for this value. This is called the base case.

If the base case is false, we can conclude that $P(n)$ is false. Hence, verifying the base case is a crucial and sometimes overlooked step in the principle of mathematical induction.

Step 3: The Inductive Hypothesis, $P(k)⟹P(k+1)$

Consider the following hypothesis: If $P(k)$ is true, then $P(k+1)$ must also be true, where $k\in \mathbb{N}$.

Suppose that $k=1$. We have already verified that $P(1)$ is true (by proving the base case). If we can prove that $P(2)$ using the fact that $P(1)$ is true, then we can repeat the process again using the fact that $P(2)$ is true, to prove $P(3)$. You can think of it like climbing a ladder. If you are on the first step of the ladder, you can use the first step to climb onto the second step. Then, you can use the second step to climb onto the third step, and so on.

However, we will not be showing that each $P(1)$, $P(2)$, $P(3)$, $\cdots$ is true directly - that's basically the same as testing $P(n)$ for each natural number. Instead, we will start off with some arbitrary value of $k\in \mathbb{N}$. By assuming that $P(k)$ is true, our goal is to show that $P(k+1)$ is true.

But how can we assume that $P(k)$ is true for some arbitrary value of $k$? This underscores the importance of verifying the base case: we must first confirm that there exists a value of $k$ for which $P(k)$ is true to start off with - otherwise we cannot reasonably make that assumption. In terms of the ladder analogy, in order to climb onto the next step, we have to be standing on a step in the first place; we cannot climb onto a step if we are floating miraculously in thin air.

Reusing the example from earlier, you would write $$\text{Assume }P(k):\sum _{r=1}^{k}r=\frac{k(k+1)}{2}\text{ for some }k\in \mathbb{N}\text{ is true.}$$

Step 4: Proving that $P(k+1)$ is true

Now that we have assumed $P(k)$ to be true, we must show that $P(k+1)$ is true using the assumption to complete the proof. This involves using $P(k)$ in some way or the other to prove that $P(k+1)$ is true. Typically, it involves algebraic manipulation and substitution.

Before this step, you should formally declare what you are required to prove. For the previous example, this step would entail $$\text{Required To Prove }P(k+1):\sum _{r=1}^{k+1}r=\frac{(k+1)[(k+1)+1]}{2}$$ $$\begin{array}{rl}\text{L.H.S.}& =\sum _{r=1}^{k+1}r\\ & =\sum _{r=1}^{k}r+\sum _{r=k+1}^{k+1}r\\ & =\sum _{r=1}^{k}r+(k+1)\text{ (Substituting }r=k+1\text{ into the summand, we obtain the }(k+1{)}^{\text{th}}\text{ term)}\\ & =\frac{k(k+1)}{2}+(k+1)(\text{ From the assumption }P(k):\sum _{r=1}^{k}r=\frac{k(k+1)}{2})\\ & =\frac{k(k+1)+2(k+1)}{2}\\ & =\frac{(k+1)(k+2)}{2}\\ & =\frac{(k+1)[(k+1)+1]}{2}\\ \text{L.H.S.}& =\text{R.H.S.}\end{array}$$ Evidently, in the example, the assumption for $P(k)$ was directly substituted to prove $P(k+1)$. However, sometimes, it may require some more work. Furthermore, note that we must manipulate the L.H.S. to look identical to the R.H.S., otherwise we may risk losing partial marks.

Step 5: Statement of Conclusion

Phew, the difficult part is over. Now, all that's left to do is formally conclude our proof with a written statement to show that we have satisfied the requirements for proof by induction. Typically, you can write, $$\text{Q.E.D. By the Principle of Mathematical Induction, }P(n)\text{ has been proven to be true }\mathrm{\forall }n\in \mathbb{N}.$$

"Q.E.D." stands for "quod erat demonstrandum", a Latin phrase which means "that which was to be demonstrated", and is typically used to conclude proofs. You should adjust this statement of conclusion depending on how $n$ has been defined (refer to step 1).

Now that we have covered the overarching logic that makes mathematical induction work, let's put pen to paper by trying some questions.

Example 1: Use mathematical induction to prove that $$1^2+3^2+5^2+\cdots +(2n-1{)}^2=\frac{n}{3}(4n^2-1)\text{ for }n\in \mathbb{N}$$ (CAPE 2014 Pure Mathematics U1 Paper 2, Caribbean Examinations Council)

Let $P(n)$ be the proposition that $$1^2+3^2+5^2+\cdots +(2n-1{)}^2=\frac{n}{3}(4n^2-1)\text{ for }n\in \mathbb{N}$$

Base Case: $P(1)$ $$\begin{array}{rl}\text{L.H.S.}& =1^2\\ & =1\\ \text{R.H.S.}& =\frac{1}{3}[4(1{)}^2-1]\\ & =\frac{1}{3}(3)\\ & =1\end{array}$$ $1=1⟹\text{L.H.S.}=\text{R.H.S.}$, confirming that $P(1)$ is true.

Assume that $P(k)$ is true for some $k\in \mathbb{N}$. $$P(k):1^2+3^2+5^2+\cdots +(2k-1{)}^2=\frac{k}{3}(4k^2-1)$$

If $P(k)$ is true, then $P(k+1)$ must also be true. $$\text{Required To Prove }P(k+1):1^2+3^2+5^2+\cdots +[2(k+1)-1{]}^2=\frac{k+1}{3}[4(k+1{)}^2-1]$$ $$\begin{array}{rl}\text{L.H.S.}& =1^2+3^2+5^2+\cdots +[2(k+1)-1{]}^2\\ & =\underset{\text{The first }k\text{ terms}}{\underbrace{1^2+3^2+5^2+\cdots +(2k-1{)}^2}}+\underset{\text{The }(k+1{)}^{\text{th}}\text{ term}}{\underbrace{[2(k+1)-1{]}^2}}\\ & =\underset{\text{The first }k\text{ terms}}{\overset{\text{(From the assumption)}}{\underbrace{\frac{k}{3}(4k^2-1)}}}+(2k+1{)}^2\\ & =\frac{1}{3}[k(4k^2-1)+3(2k+1{)}^2]\\ & =\frac{1}{3}[k(2k+1)(2k-1)+3(2k+1{)}^2]\\ & =\frac{2k+1}{3}[k(2k-1)+3(2k+1)]\\ & =\frac{2k+1}{3}(2k^2+5k+3)\\ & =\frac{2k+1}{3}(2k+3)(k+1)\\ & =\frac{k+1}{3}(2k+3)(2k+1)\\ & =\frac{k+1}{3}(4k^2+8k+3)\\ & =\frac{k+1}{3}(4k^2+8k+4-1)\\ & =\frac{k+1}{3}[4(k^2+2k+1{)}^2-1]\\ & =\frac{k+1}{3}[4(k+1{)}^2-1]\\ & =\text{R.H.S.}\end{array}$$

$$\text{Q.E.D. By the Principle of Mathematical Induction, }P(n)\text{ has been proven to be true for }n\in \mathbb{N}.$$

As you can tell, your algebraic manipulation skills need to be strong for solving these types of questions.

Example 2: Use mathematical induction to prove that ${10}^{n+1}+3({10}^n)+5$ is divisible by $9$ for all natural numbers. (CAPE 2015 Pure Mathematics U1 Paper 2 Guyana, Caribbean Examinations Council)

This type of question is called a divisibility test. The majority of the proof is similar to what you already know. However, to carry out the proof itself, divisibility tests demand a key insight about division: if the number $X$ is divisible by the number $Y$, then the quotient, $k$, must be an integer. $$\begin{array}{rl}\frac{X}{Y}& =k\\ ⟹X& =kY\end{array}$$ For instance, $10÷2=5⟹10=5\times 2$. Apply this logic in your proof.

Let $P(n)$ be the proposition that ${10}^{n+1}+3({10}^n)+5$ is divisible by $9$ $\mathrm{\forall }n\in \mathbb{N}$. $P(n)$ implies that $${10}^{n+1}+3({10}^n)+5\equiv 9A,A\in \mathbb{Z}$$

Base Case: $P(1)$ $$\begin{array}{rl}\text{L.H.S.}& ={10}^{1+1}+3({10}^1)+5\\ & =100+30+5\\ & =135\\ & =15(9)\end{array}$$ $135=15(9)$ which is divisible by $9$, confirming that $P(1)$ is true.

Assume that $P(k)$ is true for some $k\in \mathbb{N}$. $$P(k):{10}^{k+1}+3({10}^k)+5\equiv 9A$$

If $P(k)$ is true, then $P(k+1)$ must also be true. $$\text{Required To Prove }P(k+1):{10}^{(k+1)+1}+3({10}^{k+1})+5\equiv 9B\text{, }B\in \mathbb{Z}$$ $$\begin{array}{rl}\text{L.H.S.}& ={10}^{(k+1)+1}+3({10}^{k+1})+5\\ & ={10}^{k+1}\times {10}^1+3({10}^{k+1})+5\end{array}$$ We can substitute for ${10}^{k+1}$ from the assumption. Recall that $$\begin{array}{rl}{10}^{k+1}+3({10}^k)+5& =9A\\ ⟹{10}^{k+1}& =9A-5-3({10}^k)\end{array}$$ $$\begin{array}{rl}\therefore \text{L.H.S.}& =[9A-5-3({10}^k)]10+3({10}^{k+1})+5\\ & =90A-50\cancel{-3({10}^{k+1})+3({10}^{k+1})}+5\\ & =90A-45\\ & =9(10A-5)\\ & =9B\text{, where some integer }B=10A-5\\ & =\text{R.H.S.}\end{array}$$

$$\text{Q.E.D. By the Principle of Mathematical Induction, }P(n)\text{ has been proven to be true }\mathrm{\forall }n\in \mathbb{N}.$$

Example 3: Given that $S(n)=5+5^2+5^3+5^4+\cdots +5^n$, use mathematical induction to prove that $4S(n)=5^{n+1}-5$ for $n\in \mathbb{N}$. (CAPE 2015 Pure Mathematics U1 Paper 2 Rest of Region, Caribbean Examinations Council)

Firstly, don't be confused by $S(n)$. Although this looks similar to $P(n)$, $S(n)$ is simply a definition that was given in the question, not the proposition that we are being asked to prove.

Let $P(n)$ be the proposition that $4S(n)=5^{n+1}-5$ for $n\in \mathbb{N}$.

Base Case: $P(1)$ $$\begin{array}{rl}\text{L.H.S.}& =4S(n)\\ & =4(5)\because S(1)=5^1\\ & =20\\ \text{R.H.S.}& =5^{1+1}-5\\ & =25-5\\ & =20\end{array}$$ $20=20⟹\text{L.H.S.}=\text{R.H.S}$, confirming that $P(1)$ is true.

Assume that $P(k)$ is true for some $k\in \mathbb{N}$. $$P(k):4S(k)=5^{k+1}-5$$

If $P(k)$ is true, then $P(k+1)$ must also be true. $$\text{Required To Prove }P(k+1):4S(k+1)=5^{(k+1)+1}-5$$

$$\begin{array}{rl}\text{L.H.S.}& =4S(k+1)\\ & =4(5+5^2+5^3+5^4+\cdots +5^k+5^{k+1})\\ & =\underset{4S(k)}{\underbrace{4(5+5^2+5^3+5^4+\cdots +5^k)}}+4(5^{k+1})\\ & =\underset{4S(k)}{\overset{\text{(From the assumption)}}{\underbrace{5^{k+1}-5}}}+4(5^{k+1})\\ & =5(5^{k+1})-5\\ & =5^{k+2}-5\\ & =5^{(k+1)+1}-5\\ & =\text{R.H.S.}\end{array}$$

$$\text{Q.E.D. By the Principle of Mathematical Induction, }P(n)\text{ has been proven to be true for }n\in \mathbb{N}.$$

Don't forget the base case.

I know that I have emphasized this many times before, but let me show you where leaving out the base case can induce a flawed proof.

Let $P(n)$ be the proposition that $n=n+1$ $\mathrm{\forall }n\in \mathbb{W}$.

Now, obviously, we know that this proposition is false. $n=n+1⟹0=1$, which is a contradiction. However, just for the sake of highlighting the absolute necessity of the base case when doing proof by induction, let's continue by assuming that $P(k)$ is true for some $k\in \mathbb{W}$.

$$P(k):k=k+1$$

If $P(k)$ is true, then $P(k+1)$ must also be true. $$\text{Required To Prove }P(k+1):k+1=(k+1)+1$$ $$\begin{array}{rl}\text{L.H.S.}& =k+1\\ & =(k+1)+1\text{ (From the assumption, }k=k+1\text{)}\\ & =\text{R.H.S.}\end{array}$$

$$\text{Q.E.D. By the Principle of Mathematical Induction, }P(n)\text{ has been proven to be true for }n\in \mathbb{W}.$$

Now, if we had just tested the base case for $P(0)$, we would have observed that $0\ne 0+1⟹P(n)$ is false. This is why, although the base case may seem like an inconsequential step, we absolutely cannot afford to ignore it at all.