Mathematical Induction

Table of Contents

1. Introduction
2. Sum of first n natural number
3. Sum of square of first n natural number
4. Sum of cube of first n natural number
5. Complete Induction
6. Exercise

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.

1. Define the argument \(P(n)\)
2. Prove the argument for \(n=1\)
3. Prove the argument for \(n=2\)
4. Assume the argument is true for \(n=k\)
5. Prove the argument for \(n=k+1\)

---

---

---

Example 1

Prove that (ab)ⁿ=aⁿbⁿ is true for every natural number n

Solution

1. Step 1 − For n=1,(ab)¹=a¹ⁿb¹=ab, Hence, step 1 is satisfied.
2. Step 2-For n=2,(ab)²=(ab)¹⁺¹=(ab)¹(ab)¹=a¹b¹a¹b¹=a²b²
3. Step 3-For n=3,(ab)³=(ab)²⁺¹=(ab)²(ab)¹=a²b²a¹b¹=a³b³
4. Step 4(hypothesis step) − It assumes that the statement is true for the nth iteration (n=k)
5. 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+1b^k+1
   Given,
   (ab)^k=a^kb^k
   or (ab)^k (ab)=a^kb^k (ab)
   or (ab)^k+1=a^k+1b^k+1
   So,
   (ab) ⁿ=aⁿbⁿ 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

Sn	=1	+2	3	+---+	(n-2)	+(n-1)	+n
Sn	=n	+(n-1)	+(n-2)	+---+	+3	+2	+1
2Sn	=(n+1)	+(n+1)	+(n+1)	+---+	+(n+1)	+(n+1)	+(n+1)
2Sn	=n(n+1)
Sn	=\(\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.

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

After completing the basis step and the inductive step, state the conclusion, namely that by mathematical induction, P(n) is true for all integers n.

---

---

---

Exercise

Use mathematical induction for the following exercise.

1. Prove that \(3^{n-1}\) is a multiple of 2
2. Prove that \( n^3 + 2 n\) is divisible by 3
3. Prove that \((ab)^n=a^nb^n\)
4. Prove that De Moivre's theorem: \([ R (\cos x + i \sin x) ]^n = R^n(\cos n x + i \sin n x)\)
5. Find the sum of square of first \(n\) natural number algebraically
6. Find the sum of cube of first \(n\) natural number by mathematical Induction
7. Find the sum of cube of first \(n\) natural number algebraically
8. 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\)
9. 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\)
10. 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 \)