## Mathematical Induction

#### The Principle of Mathematical Induction

We will now learn about one of the most powerful tools of mathematics; the principle of mathematical induction. Its uses are manifold in all branches of mathematics. Some basic laws of addition and multiplication can be proved using this principle.

#### The principle for mathematical induction

{ p(n) | n ∈ N} is a set of statements. If p(1) is true, p(k) is true

⇒ p(k + 1) is true

and is (ii) true for p(k) ⇒ p(k + 1) is true and whenever it is true

for 1, 2, . . , n. then the statement p(n) is true for all natural numbers n.

Let us prove the following statement using the principle of mathematical induction.

#### Example

1. Prove that 1+ 3 + 5 + . . . + (2n – 1) = n2
Solution: We use the principle of induction on n. The statement p(n) is:
1+ 3 + 5 + . . . + (2n – 1) = n2
Clearly p(1) is true because 1 = 12   ——————   ( i )
Assume that the statement is true for k. (this is called the induction hypothesis)
i.e. 1+ 3 + 5 + . . . + (2k – 1) = k2   ———————   ( ii )
We have to prove the truth of p(n) for (k + 1).
Adding 2(k + 1) – 1 = 2k + 1, the term next to 2k – 1 on both sides of (ii) we find that:
1 + 3 + 5 + . . . + (2k – 1) + (2k + 1) = k2 + (2k + 1)
= (k + 1)2  —— (iii)
From (i), (ii) and (iii) we can conclude that the result p(n) is true for all natural numbers.

2. Prove that p(n): n2– 79n + 1601 is a prime.
Solution:
p(n): n2 – 79n + 1601 is a prime for n = 0, 1, 2 . . . , 79.
But for n = 80, p(n) gives (80)2 – 79 . 80 + 1601 = 412,
a composite number. Thus p(n) is not true in general though it is true for n = 0, 1, 2, 3, . . ., 79.

3. Prove that 1 + 3 + 5 + . . . + (2n – 1) = n2 + 5
Solution: Suppose p(k) 1 + 3 + 5 + . . . + (2k – 1) = k2 + 5 is true. - (1)
Now 1 + 3 + 5 + . . . + (2k – 1) + (2k + 1) = k2 + 5 + (2k + 1)
{after adding 2k+1 to both sides of equation (1) }
= (k + 1)2 + 5
That is p(k) is true. p(k+1)
But this is not true for n = 1 as 1 ≠ 6
∴  p(n): 1 + 3 + 5 + . . . + (2n – 1) = n2 + 5 is not true for all n.
By this time you might have observed that the principle basically gives a method of proof for a known formula and it is not in itself a tool for inventing the formula.

#### Try these questions

I)   Using the principle of mathematical induction prove the following

1.                                    n(n + 1)
1 + 2 + 3 + . . . + n =  —————
2

2.                                               n2(n + 1)2
13 + 23 + 33 + . . . + n3  =  —————
4

3.                                              3(3n – 1)
3 + 32 + 33 + . . . + 33  =  —————
2

4. II)    Using the principle of mathematical induction show that

5.                                                                  n(n + 1)(2n + 1)           n(n + 1)2(n + 2)
12+(12 + 22) + (12 + 22 + 32) + . . . +  ———————  =    ———————
6                                   12

6. 33n – 26 n – 1 is divisible by 676

I)    Using the principle of mathematical induction prove the following

1.                                    n(n + 1)
1 + 2 + 3 + . . . + n =  —————
2
Solution:
P(1) is true because 1(1 + 1)/2 = 1
Assume that the statement is true for k (induction hypothesis).
i.e. 1 + 2 + 3+ - - - +k = k(k+1) / 2 ----- (1)
Now to prove p(k + 1) add (k + 1) on both sides of (1)

k(k + 1)                    (k + 1)(k + 2)
1 + 2 + 3 + . . . + k + (k + 1) =  ———— + (k + 1)  =  ———————
2                                 2
∴  p(k + 1) is true
∴   p(n) is true for all n

2.                                              n2(n + 1)2
13 + 23 + 33 + . . . + n3  =  —————
4

Solution:
n2(n + 1)2
s(n) (2)    13 + 23 + 33 + . . . + n3  =  —————
4
put n = 1    L.H.S = 13 = 1

12(1 + 1)2         4
R.H.S =  —————  =  ——   =   1
4               4

L.H.S = R.H.S

k2(k + 1)2
Assume   n = k      13+ 23 + 33 + . . . + k3  =  —————    (1)
4
add (k + 1)3   to both sides of (1)
k2(k + 1)2
13 + 23 + 33 + . . . + k3 + (k + 1)3 =  ———— + (k + 1)3
4

k2(k + 1)2 + (k + 1)3
=  —————————
4

(k + 1)2 [k2 + 4(k + 1)]
=  ———————————
4
(k + 1)2 [k2 + 4k + 1]
=  ——————————
4
(k + 1)2 (k + 2)2
=  ———————
4
∴    p(k+1) is true
∴    p(n) is true for all n

3.                                         3(3n – 1)
3 + 32 + 32 + . . . + 32  =  —————
2
Solution:
n = 1     L.H.S = 31 =3. 4. II)    Using the principle of mathematical induction show that

5. ∴ P (1) is true
Let p(k) be true
that is ∴ S (k + 1) is true

6. 33n – 26n – 1 is divisible by 676
Solution:
s(n) = 33n– 26n – 1
n =1   33 (1) – 26(1) – 1
= 33 – 26 – 1
= 27 – 27 = 0    which is divisible by 676
s(1) is true
s(k) = 33 * 26k – 1
Let 3 3k - 26k - 1  = 676 p ----- (1)                [where p is integer]
⇒ Consider s(k+1)
3 (k+1)
s(k+1) = 3 - 26(k+1) - 1
=33k * 33 - 26k - 26 - 1
=33k + 26k * 33k - 26 - 1
=(33k -26k -1) + 26 * 33k - 26 ------------(2)
From (1) 33k = 676p + 26k +1
Substituting in (2)
s(k+1) = 676P + 26 ( 676p + 26K + 1) -26
=676P + 26 ( 676p + 26K + 1 - 1)
=676 + 26 ( 676p + 26K )
=676p + 26 (26) [26p + k] as 676 = 262
=676p + 676 (26p + k)
=676 [p + 26p + k] =676 (27p + K)
⇒  =33 (k+1) - 26 (k+1) - 1 is divisible by 676
∴ s (k + 1 ) is true