Chapter 2
Mathematical induction
Example 1
Use the mathematical induction principle to prove that
1+3+5+ …+ ( 2 n−1 ) =n2 ,
For all natural numbers n.
Solution
Let P ( n ) denote the statement 1+3+5+ …+ ( 2 n−1 ) =n2
(1)For n = 1,
L . H . S=1
2
R . H . S= ( 1 ) =1
L . H . S=R . H . S
The statement is true for n=1
(2)Assume that the statement is true for n = k.
2
1+3+5+ …+ ( 2 k−1 ) =k
We will have to prove that the statement is true for n = k+1
L . H . S=1+3+5+ …+ ( 2 k−1 )+[2 ( k +1 )−1]
2
= k +2 k + 2−1
= k 2+2 k +1
= ( k +1 )2
L . H . S=R . H . S
The statement is true for n=k +1
Hence, by the principal of mathematical induction,
The statement P ( n ) is true for natural numbers n.
Example 2
Use the mathematical induction principal to prove that
n ( n+1 )
1+2+3+…+ n= ,
2
For all natural numbers n.
Solution
n(n+1)
Let P ( n ) denote the statement 1+2+3+…+ n=
2
(1)For n = 1
L . H . S=1
1(1+1)
R . H . S= =1
2
L . H . S=R . H . S
The statement is true for n = 1
(2) Assume that the statement is true for n = k
k ( k +1)
1+2+3+… .+ k=
2
we will have to prove that the statement is true for n = k+1
L.H.S = 1+2+3+…+ k +k + 1
k (k +1)
= +k +1
2
2
k +k +2 k + 2
=
2
2
k +3 k +2
=
2
(k +1)(k +1+1)
R . H . S=
2
(k + 1)(k +2)
=
2
2
k +2 k +k + 2
=
2
2
k +3 k +2
=
2
L.H.S = R.H.S
The statement is true for n = k+1
Hence, by principal of mathematical induction,
The statement P ( n ) is true for natural numbers n.
Exercise 2
(1)
Prove the following by using principal of mathematic induction fo all
natural numbers n.
(a)
n
2 n−1 3 −1
1+3+3 +…+ 3 =
2
n
3 −1
Let P(n) denote the statement 1+3+32 +…+ 3n−1=
2
(1)For n = 1.
L . H . S=1
1
3 −1 2
R . H . S= = =1
2 2
L . H . S=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true for n = k,
k
2 k−1 3 −1
1+3+3 +…+ 3 =
2
We will have to prove that the statement is true for n = k+1
k +1
2 k−1 k 3 −1
1+3+3 +…+ 3 +3 =
2
2 k−1 k
L . H . S=1+3+3 +..+3 + 3
k
3 −1 k
= +3
2
k k
3 −1+2(3 )
=
2
k
3× 3 −1
=
2
k+1
3 −1
=
2
L . H . S=R . H . S
the statement is true for n=k +1
hence, by the principal of mathematical induction the statement
P ( n ) is true for natural numbers n.
*****
(b)
( )
2
n ( n+ 1 )
13 +23 +33 +…+ n3=
2
Solution
( )
2
3 3 3 n ( n+1 )
3
Let P ( n )=1 +2 +3 + …+n =
2
(1)For n = 1
3
L . H . S=1 =1
( ) ()
2
1 ( 1+1 ) 2 2 2
R . H . S= = =1 =1
2 2
L . H . S=R . H . S
… the statement is true for n = 1
(2)Assume that the statement is true for n = k
( )
2
k (k + 1)
13 +23 +33 +… k 3=
2
We have to prove that the statement is true for n = k+1
( )
2
3 3 3 3 3 ( k +1) ( k +2 )
1 +2 +3 +…+ k + ( k +1 ) =
2
3 3 3 3 3
L . H . S=1 +2 +3 +… k + ( k +1 )
( )
2
k ( k +1 )
¿ + ( k +1 )3
2
2 2
k ( k +1 )
= + ( k +1 )3
4
2 2 3
k ( k +1 ) +4 ( k +1 )
=
4
( k +1 )2 [k 2 +4 ( k +1 )3 ]
=
4
( k +1 )2 [k 2 +4 k + 4]
=
4
( k +1 ) ( k +2 )2
2
=
22
= ( )
( k +1 ) ( k +2 ) 2
2
L . H . S=R . H . S
The statement is true for n=k+1.
Hence, by the principal of mathematical induction, the statement
P ( n ) true for all natural numbers n.
*****
(c)
3 3 3 3 2 2
2 +4 +6 + …+ ( 2 n ) =2 n ( n+1 )
Solution
Let P ( n ) denote the statement 23 +4 3 +63 + …+ ( 2 n )3=2 n2 ( n+1 )2
(1) For n = 1,
3
L . H . S=2 =8
2 2 2
R . H . S=2 ( 1 ) ( 1+ 1 ) =2 ( 2 ) =8
L . H . S=R . H . S
the statement is true for n =1.
(2)Assume that the statement is true for n= k,
3 3 3 3 2 2
2 +4 +6 + …+ ( 2 k ) =2 k ( k +1 )
we will have to prove that the statement is true for n = k+1,
3 3 3 3 3 2 2
2 +4 +6 …+ ( 2 k ) + (2 k + 2 ) =2 ( k +1 ) ( k +2 )
3 3 3 3 3
L . H . S=2 + 4 +6 + …+ ( 2 k ) + ( 2 k +2 )
= 2 k 2 ( k +1 )2 + ( 2 k +2 )3
= 2 k 2 ( k +1 )2 +23 ( k +1 )3
= 2 k 2 ( k +1 )2 +8 ( k +1 )3
= 2 ( k +1 )2 [k 2 + 4 k + 4]
= 2 ( k +1 )2 ( k +2 )2
L . H . S=R . H . S
The statement is true for n = k+1
Hence, by the principal of mathematical induction
The statement P ( n ) is true for all natural numbers n.
(d)
n ( n+1 ) ( n+2 )
1.2+2.3+3.4 +…+n ( n+ 1 )=
3
Solution
n(n+1)(n+ 2)
Let P ( n ) denote the statement 1.2+2.3+3.4 +…+n ( n+ 1 )=
3
(1)For n = 1
L . H . S=1 ( 1+1 )=2
1(1+1)(1+2) 1 ×2 ×3 6
R . H . S= = = =2
3 3 3
L . H . S=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true for n = k
k ( k +1 ) ( k +2 )
1.2+2.3+3.4 +…+ k ( k +1 )=
3
We will have to prove that the statement is true for n = k+1
(k +1)(k + 2)(k +3)
1.2+2.3+3.4 +…+ k ( k +1 ) + ( k +1 ) ( k +2 )=
3
L . H . S=1.2+2.3+3.4 +…+ k ( k +1 ) +(k +1)(k +2)
k (k +1)( k +2)
= +(k +1)(k +2)
3
k ( k +1 ) ( k +2 ) +3 (k +1)(k +2)
=
3
(k + 1)(k +2)(k +3)
=
3
L . H . S=R . H . S
The statement is true for n = k+1
Hence, the principle of mathematical induction, the statement
¿ ( n ) is true for all natural numbers n.
(e)
1 1 1 1 1
+ + +…+ n =1− n
2 4 8 2 2
Solution
1 1 1 1 1
Let P ( n ) denote the statement + + +…+ n =1− n
2 4 8 2 2
(1)For n = 1
1
L . H . S=
2
1 1
R . H . S=1− 1 =
2 2
L . H . s=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true for n=k
1 1 1 1 1
+ + +…+ k =1− k
2 4 8 2 2
We will have to prove that the statement is true for n =
k+`1
1 1 1 1 1 1
+ + +…+ k + k+1 =1− k+1
2 4 8 2 2 2
1 1 1 1 1
L . H . S= + + +…+ k + k+1
2 4 8 2 2
1 1
= 1− k + k+1
2 2
1 1
= 1− k + k+1
2 2
1 1
= 1− k
+ k+1
2 2
1× 2 1
=1− k
+ k+1
2 ×2 2
2 1
= 1− k +1
+ k+1
2 2
1
= 1− k +1
2
∴L.H.S = R.H.S
Hence, by the principle of mathematical induction
The statement p(n) is true for all natural number n
(f)
2 n−1 n
1+2+2 +…+2 =2 −1
Solution
Let P ( n ) denote the statement 1+2+22 +…+2 n−1 =2n−1
(1)For n= 1
L.H.S = 1
1
R . H . S=2 −1=1
L . H . S=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true for n = k
2 k−1 k
1+2+2 +…+2 =2 −1
We will have to prove that the statement is true
for n = k+1
2 k−1 k k+1
1+2+2 +…+2 +2 =2 −1
2 k−1 k k +1
L . H . S=1+2+2 +…+ 2 + 2 =2 −1
= 2k −1+ 2k
k
2 ×2 −1
= 2k +1−1
L . H . S=R . H . S
The statement is true for n = k+1
Hence, by the mathematical induction, the
statement P ( n ) is true for all natural numbers n.
(g)
1 1 1 1 n
+ + +…+ =
1.2 2.3 3 . 4 n ( n+1 ) n+1
Let P ( n ) denote the statement
1 1 1 1 n
+ + + …+ =
1.2 2 . 3 3 . 4 n ( n+1 ) n+ 1
(1)For n = 1,
1 1
L . H . S= =
1(1+1) 2
1 1
R . H . S= =
1+1 2
L . HS =R.H.S
The statement is true for n = 1
(2)Assume that the statement is true for n = k
1 1 1 1 k
+ + + …+ =
1.2 2.3 3.4 k (k +1) k +1
we will have to prove that the statement is true for n = k+1
1 1 1 1 1 k +1
+ + + …+ + =
1.2 2. 3 3. 4 k ( k +1 ) (k +1) ( k +2 ) k +2
1 1 1 1 1
L . H . S= + + + …+ +
1 .2 2 . 3 3.4 k ( k +1 ) (k +1)(k +2)
k 1
= +
k +1 (k +1)(k +2)
k ( k +2 ) +1
=
(k + 1)(k +2)
2
k + 2 k +1
=
(k + 1)(k +2)
( k+ 1)(k +1)
=
(k + 1)(k +2)
( k+ 1)
=
(k + 2)
L . H . S=R . H . S
The statement is true for n = k+1
Hence, the statement P ( n ) is true for all natural numbers n.
Example 3
Use the mathematical induction principal to prove
that 3n −1 is a multiple of 2 for all natural numbers
n.
Solution
Let P ( n ) denote the statement 3n −1 is a multiple of
2.
For n=1
1
L . H . S=3 −1=2 (which is multiple of 2)
The statement is true for n =1
(2)Assume that the statement is true for n = k
k
3 −1 (which is multiple of 2)
We will have to prove that the statement is
true for n = k+1
k+1
L . H . S=3 −1
3 ( 3k ) −1
=(2+1) ( 3 k )−1
= 2 ( 3k ) +1 ( 3k ) −1
= 2 ( 3k ) + ( 3 k )−1
Since 2(3 k ) is a multiple of 2 and 3k −1is a
multiple of 2,
k +1
3 −1 is a multiple of 2.
The statement is true for n = k+1.
Hence, by the principle of mathematical
induction, the statement P ( n ) is true for all
natural numbers n.
Example 4
Prove that ( ab )n=a n b n for every natural numbers
n.
Solution
Let P ( n ) denote the statement ( ab )n=a n b n
(1)For n =1
1
L . H . S=( ab ) =ab
1 1
RH . S=a b =ab
L . H . S=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true for n = k
( ab )k =a k bk
We will have to prove that the statement is
true for n = k+1
( ab )k+1=ak +1 b k+1
k+ 1
L . H . S=( ab )
= ( ab )k (ab)
=(a k bk )(ab)
= ( a k .a ) ( bk . b )
= a k+1 bk +1
L . H . S =R.H.S
The statement is true for n = k+1
Hence, by the principle of mathematical
induction, the statement P ( n ) is true for all
natural numbers n.
Example 5
( 2 n−1 ) 3n+ 1+3
Prove that 1.3+2.3 2+3.3 3+ …+n . 3n=
4
for all natural numbers n by the use of the
mathematical induction principle.
solution
Let P ( n ) denote the statement
( 2 n−1 ) 3n+ 1+3
1.3+2.3 2+3.3 3+ …+n . 3n=
4
L . H . S=1.3=3
( 2−1 ) 32 +3 12
R . H . S= = =3
4 4
L . H . S=R . H . S
The statement is true for n = 1
(2)Assume that the statement is true n = k.
( 2 k−1 ) 3 k+1 +3
1.3+2 . 3+3 3.3+ …+k . 3k =
4
We will have to prove that the statement is
true for n = k+1
2 3 k k +1 ( 2 ( k +1 )−1 ) 3k +2+ 3
1.3+2 .3 +3. 3 + …+k . 3 + ( k+ 1 ) . 3 =
4
2 3 k k+1
L . H . S=1 . 3+2 .3 +3 . 3❑+…+ k .3 +(k +1).3
( 2 k−1 ) 3k+ 1+3
= + ( k + 1 ) 3 k+1
4
( 2 k−1 ) 3k+ 1+3+ 4 ( k+ 1 ) 3 k+1
=
4
( 2 k−1+ 4 k + 4 ) 3k +1+ 3
=
4
k +1
( 6 k +3 ) 3 + 3
=
4
( 2 k +1 ) 3. 3k +1+ 3
=
4
( 2 k +1 ) . 3 k+2 +3
=
4
( 2 k +2−1 ) 3k +2+3
=
4
( 2 ( k +1 )−1 ) 3k +2+ 3
=
4
… L . H . S=R . H . S
The statement is true for n = k+1
Hence, by the mathematical induction P ( n ) is
true for all natural numbers n.
(2)
Prove that 3 is a factor of 4 n−1 for all natural
numbers n by using the mathematical
induction
Solution
Let P ( n ) denote the statement 3 is a factor of
n
4 −1
(1)For n =1
L . H . S=3
So, 3 is a factor of 4 1−1
The statement is true for n = 1
(2)assume that the statement is true for n =
k.
k
4 −1
3 is a factor of 4 k −1
We will have to prove that the statement is
true for n = k+1
k +1 k
4 −1=4 .4−1
= 4. 4k −4 k +4 k −1
= 4 k ( 4−1 ) +(4 k −1)
= 3. 4 k +( 4 k −1)
3 is a factor of ( 4k −1 ) and 3 is also a factor of
k
3.4 .
So, 3 is a factor of 4 k +1−1.
The statement is true for n = k+1
Hence, by the mathematical induction, the
statement P ( n ) is true for all natural
numbers n.
(3)
Prove that n3 −n+3 is divisible by 3 for all natural numbers n by using the
mathematical induction.
Solution
Let P ( n ) denote the statement n3 −n+3is divisible by 3.
(1)For n = 1
3
1 −1+3=3 (3 is divisible by 3)
… the statement is true for n = 1.
(2)Assume that the statement is true for n = k.
3
k −k +3 is divisible by 3.
We will have to prove that the statement is true for n = k+1
( +1 )3−( k +1 ) +3
= k 3+2 k 2+ k +k 2 +2 k +1−k−1+3
= k 3+3 k 2+ 3 k +1−k −1+3
= ( k 3−k +3 ) +3 k (k +1)
Since k 3−k +3 is divisible by 3 and 3 k (k +1) is divisible by 3.
( k 3−k +3 ) +3 k ( k +1 ) is divisible by 3.
So, ( k +1 )3 −( k +1 ) +3 is divisible by 3
The statement is true for n = k+1
Hence by the mathematical induction,
the statement P ( n ) is divisible by 3 for all
natural numbers n.
(4)
Prove that 32 n−1 is divisible by 8 for all
natural numbers n by using the
mathematical induction.
Let P ( n ) denote the statement 32 n−1 is
divisible by 8.
(1) For n = 1,
2
3 −1=9−1=8
3 −1 is divisible by 8.
2
The statement is true for n = 1
(2) Assume that the statement is
true for n = k
2k
3 −1
We will have to prove that the
statement is true for n = k+1.
−1 is divisible by 8.
2 (k +1)
3
2 (k +1) 2 k+2
3 −1=3 −1
= 3 .3 −1
2k 2
= 32 k . 9−1
=32 k ×9−9+9−1
= 9 ( 32 k −1 ) +8
Since 32 k −1 is divisible by 8 and 8 is
divisible by 8.
9 ( 32 k −1 ) +8 is divisible by 8.
So, 32 (k +1)−1 is divisible by 8.
The statement is true for n = k +1
Hence, by the mathematical
induction, the statement, p(n) is true
for all natural numbers n.
(5)
Prove that ( n+1 )2 <2 n2 for all natural
numbers n≥ 3 by using the
mathematical induction.
Solution
Let P ( n )denote the statement ( n+1 )2 <2 n2
(1) For n =3
2
L . H . S=( 3+1 ) =16
2
R . H . S=2. 3 =18
L.H .S<R.H . S
So, the statement is true for n = 3
(2) Assume that the statement is
true for n = k.
( k +1 )2<2 k 2
We will have to prove that the
statement is true for n = k+1
¿
2 2
( k + 2 ) =k + 4 k + 4
= k 2+2 k +1+2 k + 3
= ( k +1 )2+2 k +3
2 2
¿ 2 k +2 k +3(…. ( k +1 ) <2 k ¿
2
= 2 k 2 +2 k +2 k −2 k +2+1
= 2 k 2 +4 k +2+1−2 k
= 2 ( k 2 +2 k +1 ) +1−2 k
= 2 ( k +1 )2 +1−2 k
(… 1−2 k < 0 , since k ≥ 3 ¿
2
¿ 2 ( k +1 )
The statement is true for n = k+1
Hence, by the principal of
mathematical induction,
The statement P ( n ) is true for all
natural numbers n ≥ 3.
(6)
example6
use the mathematical induction
principle to prove that a−b is a
factor of a n−b n for all natural
numbers n.
solution
let P ( n ) denote the statement a−b is a factor of a n−b n
(1)For n = 1
1 1
a −b =a−b
So, a−b is the factor of a 1−b1
The statement is true for n = 1
(1) Assume that the statement is true for n=k, that is a-b is the
factor of a k −b k
k k
a −b
We will have to prove that the statement is true for n = k+1
k+1 k+1
a −b
k k
a . a−b . b
= a k . a−a k b+ ak b−bk . b
k k k
a ( a−b ) +b(a −b )
Since a−bis a factor of a k ( a−b ) and a−b is a factor of a k −b k
… a−b is also a factor of a k ( a−b ) +b(ak −bk )
So, a−b is a factor of a k+1−bk+1
The statement is true for n = k+1
Hence, by the principle of mathematical induction, the statement
P ( n ) is true for all natural numbers n.
Example 7
use the mathematical induction principle to prove that 4 n<2n for all natural
numbers
n ≥ 5.
Solution
Let P ( n ) denote the statement 4 n<2n .
(1)For n =5
L . H . S=4 . 5=20
∴ L.H .S<R.H . S
5
R . H . S=2 =32
The statement is true for n = 5
(2)Assume that the statement is true n = k(k ≥ 5)
k
4 k <2
We will have to prove that the statement is true for n = k+1
k +1
4 ( k +1 ) <2
L . H . S=4 ( k +1 )=4 k +4
k k
¿ 2 + 4 (∵ 4 k <2 ¿
¿ 2 + 4 k (since 4 < 4 k ¿
k
k k k
¿ 2 +2 ( 4 k < 2 )
= 2 .2 k
= 2k +1
4 ( k +1 ) <2k +1
∴ the statement is true for n=k +1
Hence, by the principle of mathematical induction.
The statement P ( n )is true for all natural numbers n≥ 5
(7)
Prove that x 2 n− y 2 n is divisible by x + y for all natural numbers n, by using
the mathematical induction.
Solution
Let P ( n ) denote the statement s2 n− y 2 n is divisible by x + y .
For n =1
2 ( 1) 2( 1)
x −y
= x 2− y 2
= (x + y )(x− y )
x + y is a factor of x 2− y 2
x − y is divisible by x + y the statement is true for n = 1
2 2
(2)Assume that the statement is true for n = k
x − y is divisible by x + y
2k 2k
we will have prove that the statement is true for n = k+1
2 ( k+ 1) 2 ( k +1)
x −y is divisible by x + y
2 ( k+ 1) 2 ( k +1)
x −y
= x 2 k+2− y 2k +2
= x 2 k x 2− y 2 k y 2
= x 2 k x 2−x 2 k y 2+ x 2 k y 2− y 2 k y 2
= x 2 k ( x 2− y 2) + y 2 ( x 2 k − y 2 k )
Since x 2− y 2 is divisible by x + y .
∴ x 2 k ( x 2− y 2) is divisible by x + y .
Since x 2 k − y 2 k is divisible by x + y
∴ y 2 ( x 2k − y 2 k ) is divisible by x + y .
∴ x 2 k ( x 2− y 2) + y 2 ¿ is divisible by x+y.
∴ x 2(k+1 )− y 2 (k +1) is divisible by x + y
The statement is true for n = k+1
Hence, by the mathematical induction, the P ( n ) is true for all natural
numbers n.