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

1. $$Q(1)$$ holds since $$(1+8)=(2\times1+1)^{2},$$
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$$.