Mathematical Induction Examples and Solutions

This article provides examples and solutions for mathematical induction problems. It explains how to use mathematical induction to prove statements for all natural numbers. The article also introduces the concept of prime numbers, divisors, GCD and LCM with examples.

1)
∑
k =1
n
k ( k +1 )= 1
3 n ( n+1 ) ( n+2 )
LHS=RHS for k=n=1
That is P(1) is true.
Assume P(k) is true and P(n) is true.
P(k)=
∑
k =1
n
k ( k +1 )
P(n)= 1
3n(n+1)(n+2)
= 1
3 ( n3 +3 n2 +2 n)
We need to prove P(k+1) & P(n+1) is true.
LHS=,
P(k+1)=
∑
k =1
n
( k +1 ) ( k +2 )
∑
k =1
n
(k2 +3 k + 2)
¿ ∑
k=1
n
k 2+∑
k=1
n
3 k +∑
k=1
n
2
= n ( n+1 ) ( 2 n+1 )
6 + 3 n ( n+1 )
2 +2 n
¿ n ( 2 n2+3 n+ 1 ) +9 n2 +9 n+12 n
6
¿ 2n3+12 n2 +22 n
6
¿ 1
3 ( n3 +6 n2+11n )
RHS,

P(n+1)=
¿ 1
3 ( ( n+ 1 )3+3 ( n+ 1 )2+2 ( n+1 ) )
¿ 1
3 ( n3 +6 n2+ 11n+6 )
¿ 1
3 ( n3 +6 n2+ 11n ) + 1
3∗6
Where the last term is a multiple of n3 +6 n2+11 n.
Therefore LHS=RHS
Therefore P(k+1) and P(n+1) is also true whenever P(k) and P(n) is true.
Hence, by mathematical induction, P(n) and P(k) is true for all n, k ϵ N.
2) To prove 2n+1 is less than n2 +3
Let P(n): 2n+1<n2 +3
P(1): 3<4, which is true.
Assume P(k) is true.
P(k):
2k+1<k 2+3
We have to prove P(k+1) is also true.
P(k+1):
LHS: 2k+3
RHS: (k + 1)2 +3
=k 2+2 k +1+3
=k 2+2 k + 4
=k(k+2)+4
Which is greater than LHS.
Therefore P(k+1) is also true whenever P(k) is true.
Hence, by mathematical induction P(n) is true for all n ϵ N.

3)
∑
k =1
n
3k= 1
2 ( 3n +1−3 )
Let P(n): ∑
k =1
n
3k= 1
2 ( 3n +1−3 )
P(1)=
LHS, =3
RHS, =3
Therefore P(1) is true.
Assume P(k) is true,
P(k):
LHS =
∑
k =1
n
3k
¿ 3+32 +33 … … …+3k
This is equal to RHS,
That is, 3+32 +33 … … …+3k= 1
2 ( 3k+1−3 )
We need to prove P(k+1) is also true,
P(k+1)=
∑
k +1=1
k
3k+1
¿ 3+32 +33 + …3k+3k+1
¿ 1
2 ( 3k +1−3 ) +3k+1
¿ ( 1
2 +1 ) 3k +1− 3
2
¿ 3
2 ( 3k+1 )− 3
2

¿ 3k+2 −3
2
Which is equal to RHS,=
1
2 (3k+2−3)
Therefore LHS = RHS,
Therefore P(k+1) is true whenever P(k) is true,
Hence by mathematical induction, P(n) is true for all n ϵ N.
4) To prove 25n +5n is a multiple of 10
Let P(n)= 25n +5n
P(1)= 25+5
=30 which is a multiple of 10
Therefore P(1) is true.
Assume P(k) is true,
P(k)= 25k +5k
We need to prove P(k+1) is true,
P(k+1)= 25k +1+ 5k+1
= 25k .25+5k .5
=25(25k +5k−5k ¿+5k .5
=25(10p- 5k ¿+5k .5, where 25k +5k is a multiple of 10=10 p
=25*10p-25 ¿ 5k +5*5k
=25*10p-20* 5k
Which is a multiple of 10.
Therefore P(k+1) is true whenever P(k) is true.
Hence by mathematical induction P(n) is true for all n ϵ N.
5)

an+1=2 an , a0=1
Putting n=0,
a1=2∗a0
¿ 2
Putting n=1,
a2=2 a1
¿ 4
Similarly, a3=8 , a4 =16 …∧so on
In general, an=2n ,n ϵ N.
Let P(n): an=2n
P(1)=a1=¿ 21
Which is true.
Assume P(k) is true,
P(k)= ak=2k ,
To prove P(k+1),
P(k+1)= ak+1=2k+1
= 2* 2k
That is ak+1=2∗ak
Therefore P(k+1) is true whenever P(k) is true.
Hence by mathematical induction, P(n) is true for all nϵN.
6) 877 is a prime number.
877 is not divisible by the following prime numbers :-
2,3,5,7,11,13,17,19,23,29
By 2,
877
2 =438.5
which is not a whole number,

By 3,
877
3 =292.333
which is not a whole number,
By 5,
877
5 =175.4
which is not a whole number,
By 7,
877
7 =125.285
which is not a whole number,
By 11,
877
11 =79.72
which is not a whole number,
By 13,
877
13 =67.46
which is not a whole number,
By 17,
877
17 =51.588
which is not a whole number,
By 19,
877
19 =46.15
which is not a whole number,
By 23,
877
23 =38.13

which is not a whole number,
By 29,
877
29 =30.24
which is not a whole number.
7)
p is a prime greater than 2, p+1 cannot be prime,
Let p =3,
p+1=4, which is divisible by 2,
Let p=5,
p+1 =6, which is divisible by 2 & 3
Let p=7,
p+1=8,
Let p=11,
p+1=12
and so on…
p+1 is always even,
Therefore, p+1 cannot be prime.
8)
p & p+2 are both prime – pair of twin primes.
p>10,
let p=11,
p+2=13
Therefore they are twin primes,
Let p=17
p+2=19
Therefore they are twin primes,

Let p=41,
p+2=43, they are twin primes,
Therefore there exists twin primes p,p+2 with p>10.
9)
2221=a
2237=b
2239=c
2243=d,
If a
b = c
d ,
then ,a∗d =b∗c
But here a
b ≠ c
d ,
Therefore, a∗d ≠ b∗c
10)
51984−1 cannot be prime
5n −1 is always even,
Therefore, 51984−1 cannot be prime
11)
a)list of all positive divisors of p2 q3= p,q,1
b)GCD of p4 q4∧ p6 q3= p4 q3
c)LCM of p4 q4∧ p6 q3= p6 q4
12)
GCD of 35&10 using Euclidean Algorithm,
GCD of (10,35)=
35= 10q+r
35=10*3 + 5
10=5*2+0

Therefore GCD = 5
LCM*GCD= product of two numbers
LCM*5=350
LCM=70
13)
GCD of two numbers = 3, LCM=30
GCD*LCM= product of two numbers;
3*30=a*b
Therefore the two numbers are 3 and 30.
(here the product is 90 therefore the only numbers are 3 & 30)
14)
GCD=5
LCM=11
GCD*LCM=55
Therefore it is not possible to have two positive integers with GCD=5 &
LCM=11 as 55 is only divisible by 5 and 11.