Mathematical Induction
1.0 Introduction
1.0 Introduction
This chapter explains a powerful proof technique called mathematical induction. To motivate the discussion, let’s us first examine the kinds of statements in which induction is used to prove.
Consider the following statement.
The sum of the first $n$ odd natural numbers equals ${n^2}$. The following table illustrates what this conjecture says. Each row is headed by a natural number $n$, followed by the sum of the first $n$ odd natural numbers, followed by ${n^2}$.
| $n$ | Sum of the first $n$ odd natural numbers | ${n^2}$ |
| 1 | $1=....................$ | $1$ |
| 2 | $1+3=.................$ | $4$ |
| 3 | $1+3+5=..................$ | $9$ |
| 4 | $1+3+5+7=..................$ | $16$ |
| 5 | $1+3+5+7+9=..................$ | $25$ |
| $.$ | $....$ | $..$ |
| $.$ | $....$ | $..$ |
| $.$ | $....$ | $..$ |
| $.$ | $....$ | $..$ |
| n | $1+3+5+7+9+11+.....+(2n-1)=...............$ | ${n^2}$ |
Note that in the first five lines of the table, the sum of first $n$ odd numbers add up to ${n^2}$. We can notice that these first five lines indicate that the $nth$ odd natural number which is the last term in each sum (=$2n-1$). (For instance, when $n = 2$, the second odd natural number is $2 \times 2 - 1 = 3$; when $n = 3$, the third odd natural number is $2 \times 3 - 1 = 5$, etc.).
The table raises a question. Does the sum $1+3+5+7+···+(2n?1)$ really always equal to ${n^2}$? In other words, Is the above statement true?
Let’s consider it again as follows. For each natural number $n$ (i.e., for each line of the table), we have a statement ${S_n}$, as follows:
$$\begin{equation} \begin{aligned} {S_1}:1 = {1^2} \\ {S_2}:1 + 3 = {2^2} \\ {S_3}:1 + 3 + 5 = {3^2} \\\end{aligned} \end{equation} $$
$${S_n}:1 + 3 + 5 + 7 + 9 + ....... + (2n - 1) = {n^2}$$
Our question is: Are all of above statements true? Mathematical induction is designed to answer just such kind of question. It is used when we have set of statements ${S_1}$,${S_2}$,${S_3}$...${S_n}$ and we need to prove that they are all true. The method is really quite simple. To visualize it, think of the statements as dominoes, lined up in a row. Imagine you can prove the first statement ${S_1}$, and symbolize this as domino ${S_1}$ being knocked down. Additionally, imagine that you can prove that any statement ${S_k}$ being true (falling) forces the next statement ${S_k+1}$ to be true (to fall). Then ${S_1}$ falls, and knocks down ${S_2}$. Next ${S_2}$ falls and knocks down ${S_3}$, then ${S_3}$ knocks down ${S_4}$, and so on. The inescapable conclusion is that all the statements are knocked down (proved true).
This picture gives the idea about the mathematical induction.
Our key basis of mathematical thinking is logical deduction. An informal example of deductive reasoning, borrowed from logical study can be explained by a following example
(i) All dancers are thin.
(ii) Rohan Sir is dancer.
(iii) Rohan sir is thin.
So if statements (i) and (ii) are true then the (iii) statement is also true.
Deduction in a nutshell is given a statement to be proven, often called a conjecture or a theorem in mathematics, valid deductive steps are derived and a proof may or may not be established, i.e., deduction is the application of a general case to a particular case.
In algebra, there are certain results or statements that are formulated in terms of $n$, where $n$ is a positive integer. To prove such statements the well-suited principle that is used and based on the specific technique, is known as the principle of mathematical induction.
Motivation: To understand the basic principles of mathematical induction, consider a set of thin rectangular tiles which are placed on one end, as shown in figure. When the first tile fall down, all the tiles will fall down. To absolutely sure that all tiles will fall, it is sufficient to know that(i) The first tile falls down.
(ii) In the event that any tile falls its successor necessarily falls.
This is the basic underlying principle of mathematical induction .
