Mathematical Induction

After finding that some mathematical identity is true for some natural numbers (as in the examples presented in these pages), there is a good method to confirm and prove the truth of that identity for ALL natural numbers: the mathematical induction principle.

Suppose, for instance, that we would like to investigate the truth of the identity


for every natural number \(n\).

Let us designate this identity by \(P(n)\). We have to start by checking the truth of \(P(1)\), which is obvious in this case: \(1=1^{2}\).

Then, we suppose that the identity is valid for a natural \(n-1\):

\(\;\;\;\;\;\;\,1+3+5+...+(2(n-1)-1)=(n-1)^{2} \Longleftrightarrow \\ \Longleftrightarrow1+3+5+...+(2n-3)=(n-1)^{2}\)

It suffices then to show that \(P(n)\) is also valid. This is true in this example, since

\(\;\;\;1+3+5+...+(2n-1)=\\ =1+3+5+...+(2n-3)+(2n-1)=\\ =(n-1)^{2}+(2n-1)=\\ =n^{2}-2n+1+2n-1=\\=n^{2}\)

where the second equality holds by the truth of \(P(n-1)\).

This means that, if \(P(1)\) holds, then also \(P(2)\) holds. Appplying this reasoning again and again (for \(n=3,4,5,...\)), we guarantee that \(P(n)\) holds for every natural \(n\).

\[\begin{array}{ccccccccc} P_{(1)} & \Longrightarrow & P_{(2)} & \Longrightarrow & P_{(3)} & \Longrightarrow & P_{(4)} & \Longrightarrow & ...\\ & (n=2) & & (n=3) & & (n=4) & & (n=5) \end{array}\]

In summary, the induction method consists on the following steps:

1. To show the truth of \(P(1);\)

2. To show that \(P_{(n-1)}\Longrightarrow P_{(n)}\) for every natural \(n\).

Let us see another example:


  1. \(Q(1)\) holds since \((1+8)=(2\times1+1)^{2},\)
  2. Suppose that \(Q(n-1)\) is true, that is,



\(\;\;\;1+8+16+...+8(n-1)+8n=\\ =(2n-1)^{2}+8n=\\ = 4n^{2}-4n+1+8n=4n^{2}+4n+1=\\ =(2n+1)^{2},\)

which means that \(Q(n-1)\Longrightarrow Q(n)\) and, thus, the statement \(Q(n)\) holds for every natural number \(n\).

(*) Difficulty level: Upper Secondary