Math without words (*) 
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\).
