### 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

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

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:

\[Q(n):1+8+16+24+...+8n=(2n+1)^{2}\]

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

\[1+8+16+24+...+8(n-1)=(2n-1)^{2}.\]

Then

\(\;\;\;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\).