#### Introduction

The NATURAL NUMBERS are the counting numbers: 1, 2, 3, 4, etc. Based on it, the Mathematical induction is a technique for proving a statement that is asserted about every natural number. By "every", or "all," natural numbers, we mean any one that we name.

Thus,

Mathematical induction is a proof technique. It is a form of direct proof, and it is done based on natural numbers in following steps.

- Define the argument \(P(n)\)
- Prove the argument for \(n=1\)
- Prove the argument for \(n=2\)
- Assume the argument is true for \(n=k\)
- Prove the argument for \(n=k+1\)

#### Example 1

Prove that (ab)^{n}=a^{n}b^{n} is true for every natural number n

Solution

- Step 1 − For n=1,(ab)
^{1}=a^{1n}b^{1}=ab, Hence, step 1 is satisfied. - Step 2-For n=2,(ab)
^{2}=(ab)^{1+1}=(ab)^{1}(ab)^{1}=a^{1}b^{1}a^{1}b^{1}=a^{2}b^{2} - Step 3-For n=3,(ab)
^{3}=(ab)^{2+1}=(ab)^{2}(ab)^{1}=a^{2}b^{2}a^{1}b^{1}=a^{3}b^{3} - Step 4(hypothesis step) − It assumes that the statement is true for the nth iteration (n=k)
- Step 5(Inductive ste) − It proves that a statement is true for the value n=k+1

We have to prove that (ab)^{k+1}=a^{k+1}b^{k+1}

Given,

(ab)^{k}=a^{k}b^{k}

or (ab)^{k}(ab)=a^{k}b^{k}(ab)

or (ab)^{k+1}=a^{k+1}b^{k+1}

So,

(ab)^{n}=a^{n}b^{n}is true for every natural number n.

### Sum of first \( n\) natural number

##### Mathematical Induction Method

Show that sum of first \( n\) natural number is \(\frac{n( n+1 )}{2}\) by induction.

Proof

Step 1 Show that the statement holds for \( n = 1\) .

\( P(1) = 1=1\) (E1)

The result is

\( \frac{n(n+1)}{2}=\frac{1(1+1)}{2}=\frac{1.2}{2}=1\) (F1)

It shows that, (E1=F1), the statement is true for n=1

Step 2 Show that the statement holds for \( n = 2\) .

\( P(2) = 1+2 =3\)(E2)

The result is

\( \frac{n(n+1)}{2}=\frac{2(2+1)}{2}=\frac{2.3}{2}=3\) (F2)

It shows that, (E2=F2), the statement is true for n=2

Step 3 Show that the statement holds for \( n = 3\) .

\( P(3) = 1+2+3=6\)(E3)

The result is

\( \frac{n(n+1)}{2}=\frac{3(3+1)}{2}=\frac{3.4}{2}=6\) (F3)

It shows that, (E3=F3), the statement is true for n=3

Step 4 Assume that the statement holds for \( n = k\)

\( P(k) = 1+2+3+...+k\)

The result is

\( \frac{k(k+1)}{2}\)

We assume that,

\(1+2+3+...+k=\frac{k(k+1)}{2}\) (H)

Step 5 Verify that the statement holds for \( n = k+1\) .

\( P(k+1) = 1+2+3+...+k+(k+1)\)

The result is

\( P(k+1) = 1+2+3+...+k+(k+1)\)

or \(P(k+1) = [1+2+3+...+k]+(k+1)\)

or \(P(k+1) = \frac{k(k+1)}{2}+(k+1) \)

or \(P(k+1) = (k+1)( \frac{k}{2}+1 ) \)

or \(P(k+1) = (k+1)( \frac{k+2}{2} ) \)

or \(P(k+1) = \frac{(k+1)[(k+1 )+1]}{2} \)

or \(P(n) = \frac{n(n+1)}{2} \)

This shows that the statement is true for \( n=k+1\) .

Thus, for any natural number \( n\) , we have,

\( 1+2+3+...+n = \frac{n(n+1)}{2}\)

This completes the proof.

##### Geometrical Method

चित्रमा दुईवटा 1+2+3+…+8 को योगलाई आयताकार रुपमा प्रस्तुत गरिएको छ। जसमा,

\(S_8=1+2+3+…+8\)

or \(2S_8= \)आयतको क्षेत्रफल

or \(S_8=\frac{1}{2}\) आयतको क्षेत्रफल

or \(S_8=\frac{1}{2}\) लम्बाई x चौडाई

or \(S_8=\frac{1}{2} (8+1) \times 8\)

यसै गरि 1+2+3+…+n हुँद, adding the natural numbers up to n, twice, we get

S_{n} |
=1 | +2 | 3 | +---+ | (n-2) | +(n-1) | +n |

S_{n} |
=n | +(n-1) | +(n-2) | +---+ | +3 | +2 | +1 |

2S_{n} |
=(n+1) | +(n+1) | +(n+1) | +---+ | +(n+1) | +(n+1) | +(n+1) |

2S_{n} |
=n(n+1) | ||||||

S_{n} |
=\(\frac{n(n+1)}{2} \) |

Therefore,

\(S_n= \frac{1}{2} (n+1) \times n \)

or \( S_n= \frac{n(n+1)}{2}\)

##### Algebraic Method

Show that sum of first \( n\) natural number is \(\frac{n( n+1 )}{2}\) by induction.

Proof

We know that,

\(r^2-(r-1)^2=2r-1\)

Thus, taking the values from r=1,2,...n, and then summing up, we get

Taking r=1 | \(1^2-(1-1)^2=2.1-1\) |

Taking r=2 | \(2^2-(2-1)^2=2.2-1\) |

Taking r=3 | \(3^2-(3-1)^2=2.3-1\) |

Taking r=4 | \(4^2-(4-1)^2=2.4-1\) |

\(\cdots \) | \(\cdots \) |

Taking r=n | \(n^2-(n-1)^2=2.n-1\) |

Summing up r=1 to n | \(n^2=2(1+2+3+..+n)-1.n\) |

As we know, \(S_n=1+2+3+..+n\), so from the sum, we can write

\(2S_n= n^2+n\)

or\(S_n= \frac{n(n+1)}{2}\)

### Sum of square of first \( n\) natural number

##### Mathematical Induction Method

Show that sum of square of first \( n\) natural number is \(\frac{n( n+1 )( 2n+1 )}{6}\) by induction.

Proof

Step 1 Show that the statement holds for \( n = 1\) .

\( P(1) = 1^2=1\) (E1)

The result is

\( \frac{n(n+1)( 2n+1 )}{6}=\frac{1(1+1)( 2.1+1 )}{6}=\frac{1.2.3}{6}=1\) (F1)

It shows that, (E1=F1), the statement is true for n=1

Step 2 Show that the statement holds for \( n = 2\) .

\( P(2) = 1^2+2^2 =5\)(E2)

The result is

\( \frac{n(n+1)( 2n+1 )}{6}=\frac{2(2+1)( 2.2+1 )}{6}=\frac{2.3.5}{6}=5\) (F2)

It shows that, (E2=F2), the statement is true for n=2

Step 3 Show that the statement holds for \( n = 3\) .

\( P(3) = 1^2+2^2+3^2 =12\)(E3)

The result is

\( \frac{n(n+1)( 2n+1 )}{6}=\frac{3(3+1)( 2.3+1 )}{6}=\frac{3.4.7}{6}=14\) (F3)

It shows that, (E3=F3), the statement is true for n=3

Step 4 Assume that the statement holds for \( n = k\)

\( P(k) = 1^2+2^2 +3^2+4^2+…..+k^2\)

The result is

\( \frac{k(k+1)( 2k+1 )}{6}\)

We assume that,

\(1^2+2^2 +3^2+4^2+…..+k^2=\frac{k(k+1)( 2k+1 )}{6}\) (H)

Step 5 Verify that the statement holds for \( n = k+1\) .

\( P(k+1) = 1^2+2^2 +3^2+4^2+…..+k^2+ (k+1)^2\)

The result is

\( P(k+1) = (1^2+2^2 +3^2+4^2+…..+k^2)+ (k+1)^2\)

or \(P(k+1) = \frac{k(k+1)( 2k+1 )}{6}+(k+1)^2\)

or \(P(k+1) = (k+1)\{ \frac{k( 2k+1 )}{6}+(k+1) \}\)

or \(P(k+1) = (k+1)\{ \frac{k( 2k+1 )+6(k+1)}{6} \}\)

or \(P(k+1) = (k+1)\{ \frac{2k^2 +7k+6}{6} \}\)

or \(P(k+1) = (k+1)\{ \frac{( 2k+3 )(k+2)}{6} \}\)

or \(P(k+1) = (k+1)\{ \frac{( 2k+2+1 )(k+1+1)}{6} \}\)

or \(P(k+1) = (k+1)\{ \frac{( 2(k+1)+1 )(( k+1 )+1)}{6} \}\)

or \(P(n) = \frac{n(n+1)( 2n+1 )}{6} \)

This shows that the statement is true for \( n=k+1\) .

Thus, for any natural number \( n\) , we have,

\( 1^2 +2^2 +3^2 +....+n^2 = \frac{n(n+1)( 2n+1 )}{6}\)

This completes the proof.

##### Geometrical Method

The length of the cube is 1 unit, the volume of cube is 1 cubic unit. In this case, the volume non-shaded region=1 in first figure, the volume of non-shaded region =\(\frac{2}{3}\) in second figure, and the of the volume non-shaded region=\(\frac{1}{2}\) in third figure. Let \( V_n\) be the sum of volume of first \( n^2\) bricks, then

\( V_2 =\frac{1}{3}(2^3 )+\frac{2}{3}(2)+\frac{1}{2}(0+2)

\)

This is shown as below

Also,

\( V_3 =\frac{1}{3}(3^3 )+\frac{2}{3}(3)+\frac{1}{2}(0+2+4)

\)

this is also shown in the figure below

Also

\( V_4 =\frac{1}{3}(4^3 )+\frac{2}{3}(4)+\frac{1}{2}(0+2+4+6)

\)

This is shown in a figure below.

Similarly,

\( V_n=\frac{1}{3}(n^3 )+\frac{2}{3}(n)+\frac{1}{2}[0+2+4+6+2(n-1)] \)

or \( V_n=\frac{1}{3}(n^3 )+\frac{2}{3}(n)+\frac{1}{2}\times 2[0+1+2+3+(n-1)] \)

or \( V_n=\frac{1}{3}(n^3 )+\frac{2}{3}(n)+[1+2+3+(n-1)+n-n ]\)

or \( V_n=\frac{1}{3}(n^3 )+\frac{2}{3}(n)+\frac{n(n+1)}{2}-n \)

or \( V_n=\frac{2n^3 +4n+3{{n}^{2}}+3n-6n}{6}\)

or \( V_n=\frac{2n^3 +3{{n}^{2}}+n}{6}\)

or \( V_n=\frac{n( n+1 )( 2n+1 )}{6}\)

### Sum of cube of first \( n\) natural number

##### Geometrical Method

Find the sum of cube of first nnatural number geometrically

Let us take sum of first five cubes of natural numbers, viz. \(1^3+2^2+3^3+4^3+5^3\), where

\( 1^3=1, 2^3=2 \times 2^2 ,3^3=3 \times 3^2, 4^3=4 \times 4^2 , 5^3=5 \times 5^2\)

In the figure below

\(1^3+2^2+3^3+4^3+5^3\) are added to from a rectangle

The result is a square of length \(l=\frac{n(n+1)}{2}\) which is in this case \(l=1+2+3+4+5=15\)

Therefore, the sum of cubes of first \(n\) natural number is

\(1^3+2^2+3^3+4^3+5^3+...+n^3\)=Area of square [ length \(l=1+2+3+4+5+...+n\)]

We know that,

\(l=1+2+3+4+5+...+n=\frac{n(n+1)}{2}\)

Therefore

\(1^3+2^2+3^3+4^3+5^3+...+n^3=\) Area of square [ length \(l=\frac{n(n+1)}{2}\)]

or \(1^3+2^2+3^3+4^3+5^3+...+n^3=\left [\frac{n(n+1)}{2} \right ]^2\)

This completes the proof.

### Complete Induction

When we use induction to prove that \(P(n)\) is true for all natural numbers \(n\), our inductive hypothesis is the assumption that \(P(i)\) is true for \(i= 1, 2,...,k\). That is, the inductive hypothesis includes all \(k\) statements \(P(1), P(2),...,P(k)\). Because we can use all \(k\) statements \(P(1), P(2),...,P(k\) true to prove \(P(k+ 1)\), is true. Because of this, some mathematicians prefer to always use strong induction instead of mathematical induction, even when a proof by mathematical induction is easy to compute. Strong induction is sometimes called the second principle of mathematical induction or complete induction. It is defined as below.

- Express the statement that is to be proved in the form \(P(n)\).
- Show that \(P(1)\) is true
- State the inductive hypothesis, and assume that \(P(k)\) is true
- Show that \([P(1)\land P(2) \land \cdots \land P(k)] \to P(k+ 1)\) is true

### Exercise

Use mathematical induction for the following exercise.- Prove that \(3^{n-1}\) is a multiple of 2
- Prove that \( n^3 + 2 n\) is divisible by 3
- Prove that \((ab)^n=a^nb^n\)
- Prove that De Moivre's theorem: \([ R (\cos x + i \sin x) ]^n = R^n(\cos n x + i \sin n x)\)
- Find the sum of square of first \(n\) natural number algebraically
- Find the sum of cube of first \(n\) natural number by mathematical Induction
- Find the sum of cube of first \(n\) natural number algebraically
- Prove the binomial theorem using mathematical induction. The binomial theorem states that for any positive integer n, \((a+b)^n=\displaystyle \sum_{k=0}^{n} \begin {pmatrix} n \\ k \end{pmatrix} a^{n-k}b^k\)
- Prove Pascal's Identity using mathematical induction \(\begin {pmatrix} n \\ k \end{pmatrix}=\begin {pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin {pmatrix} n-1 \\ k \end{pmatrix}\) for all positive integers n and k such that \(1 \le k \le n-1\)
- Prove that for all positive integers n and for any real number \(r\ne 1\) the sum of the first n terms of a geometric series is given by the formula \(S_n=\frac{a(1-r^n)}{1-r}\), where a is the first term.

#### Example 7

Show that sum of cube of first n natural number is S_{n}=\(\left (\frac{n(n+1)}{2} \right )^2 \)

Suppose that \(1^3+2^3+3^3+...+n^3\) =S_{n}, then we start from

\( r^4-(r-1)^4\) | \(=4 r^3- 6 r^2+ 4 r-1\) | |

Taking r=1 | \(1^4-0^4\) | \(=4 \times 1^3- 6 \times 1^2+ 4\times 1-1 \) |

Taking r=2 | \(2^4-1^4\) | \(=4 \times 2^3- 6 \times 2^2+ 4\times 2-1 \) |

Taking r=3 | \(3^4-2^4\) | \(=4 \times 3^3- 6 \times 3^2+ 4\times 3-1\) |

............................. | ............................ | ............................ |

Taking r=(n-1) | \((n-1)^4-(n-2)^4\) | \(=4 \times (n-1)^3- 6 \times (n-1)^2+ 4\times (n-1)-n \) |

Taking r=n | \(n^4-(n-1)^4\) | \(=4 \times n^3- 6 \times n^2+ 4\times n-1\) |

Adding, we get

\( n^4=4 (1^3+2^3...+ n^3)- 6 (1^2+2^2+...+ n^2)+ 4(1+2...+n)-n \)

or
\(n^4\)=4 (S_{n})- \(6 \frac{n(n+1)(2n+1)}{6}+ 4 \frac{n(n+1)}{2}-n \)

or
4 (S_{n})=\( n^4+ n(n+1)(2n+1)- 2 n(n+1)+n \)

or
4S_{n}= \( n^4+ 2 n^3 +n^2 \)

or
S_{n}=\( \left (\frac{n(n+1)}{2} \right )^2 \)

## No comments:

## Post a Comment