Mathematical Induction - Problems With Solutions

Several problems with detailed solutions on mathematical induction are presented.

The principle of mathematical induction is used to prove that a given proposition (formula, equality, inequality…) is true for all positive integer numbers greater than or equal to some integer N.
Let us denote the proposition in question by P (n), where n is a positive integer. The proof involves two steps:
Step 1: We first establish that the proposition P (n) is true for the lowest possible value of the positive integer n.
Step 2: We assume that P (k) is true and establish that P (k+1) is also true

Problem 1

Use mathematical induction to prove that
1 + 2 + 3 + ... + n = n (n + 1) / 2
for all positive integers n.
Solution to Problem 1:
Let the statement P (n) be
1 + 2 + 3 + ... + n = n (n + 1) / 2
STEP 1: We first show that p (1) is true.
Left Side = 1
Right Side = 1 (1 + 1) / 2 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 + 2 + 3 + ... + k = k (k + 1) / 2
and show that p (k + 1) is true by adding k + 1 to both sides of the above statement
1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) / 2 + (k + 1)
= (k + 1)(k / 2 + 1)
= (k + 1)(k + 2) / 2
The last statement may be written as
1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2) / 2
Which is the statement p(k + 1).

Problem 2

Prove that
1 ² + 2 ² + 3 ² + ... + n ² = n (n + 1) (2n + 1)/ 6
For all positive integers n.
Solution to Problem 2:
Statement P (n) is defined by
1 ² + 2 ² + 3 ² + ... + n ² = n (n + 1) (2n + 1)/ 2
STEP 1: We first show that p (1) is true.
Left Side = 1 ² = 1
Right Side = 1 (1 + 1) (2*1 + 1)/ 6 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 ² + 2 ² + 3 ² + ... + k ² = k (k + 1) (2k + 1)/ 6
and show that p (k + 1) is true by adding (k + 1) ² to both sides of the above statement
1 ² + 2 ² + 3 ² + ... + k ² + (k + 1) ² = k (k + 1) (2k + 1)/ 6 + (k + 1) ²
Set common denominator and factor k + 1 on the right side
= (k + 1) [ k (2k + 1)+ 6 (k + 1) ] /6
Expand k (2k + 1)+ 6 (k + 1)
= (k + 1) [ 2k ² + 7k + 6 ] /6
Now factor 2k ² + 7k + 6.
= (k + 1) [ (k + 2) (2k + 3) ] /6
We have started from the statement P(k) and have shown that
1 ² + 2 ² + 3 ² + ... + k ² + (k + 1) ² = (k + 1) [ (k + 2) (2k + 3) ] /6
Which is the statement P(k + 1).

Problem 3

Use mathematical induction to prove that
1 ³ + 2 ³ + 3 ³ + ... + n ³ = n ² (n + 1) ² / 4
for all positive integers n.

Solution to Problem 3:

Statement P (n) is defined by
1 ³ + 2 ³ + 3 ³ + ... + n ³ = n ² (n + 1) ² / 4
STEP 1: We first show that p (1) is true.
Left Side = 1 ³ = 1
Right Side = 1 ² (1 + 1) ² / 4 = 1
hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 ³ + 2 ³ + 3 ³ + ... + k ³ = k ² (k + 1) ² / 4
add (k + 1) ³ to both sides
1 ³ + 2 ³ + 3 ³ + ... + k ³ + (k + 1) ³ = k ² (k + 1) ² / 4 + (k + 1) ³
factor (k + 1) ² on the right side
= (k + 1) ² [ k ² / 4 + (k + 1) ]
set to common denominator and group
= (k + 1) ² [ k ² + 4 k + 4 ] / 4
= (k + 1) ² [ (k + 2) ² ] / 4
We have started from the statement P(k) and have shown that
1 ³ + 2 ³ + 3 ³ + ... + k ³ + (k + 1) ³ = (k + 1) ² [ (k + 2) ² ] / 4
Which is the statement P(k + 1).

Problem 4

Prove that for any positive integer number n , n ³ + 2 n is divisible by 3
Solution to Problem 4:

Statement P (n) is defined by
n ³ + 2 n is divisible by 3
STEP 1: We first show that p (1) is true. Let n = 1 and calculate n ³ + 2n
1 ³ + 2(1) = 3
3 is divisible by 3
hence p (1) is true.
STEP 2: We now assume that p (k) is true
k ³ + 2 k is divisible by 3
is equivalent to
k ³ + 2 k = 3 M , where M is a positive integer.
We now consider the algebraic expression (k + 1) ³ + 2 (k + 1); expand it and group like terms
(k + 1) ³ + 2 (k + 1) = k ³ + 3 k ² + 5 k + 3
= [ k ³ + 2 k] + [3 k ² + 3 k + 3]
= 3 M + 3 [ k ² + k + 1 ] = 3 [ M + k ² + k + 1 ]
Hence (k + 1) ³ + 2 (k + 1) is also divisible by 3 and therefore statement P(k + 1) is true.

Problem 5

Prove that 3 ⁿ > n ² for n = 1, n = 2 and use the mathematical induction to prove that 3 ⁿ > n ² for n a positive integer greater than 2.
Solution to Problem 5:

Statement P (n) is defined by
3 ⁿ > n ²
STEP 1: We first show that p (1) is true. Let n = 1 and calculate 3 ¹ and 1 ² and compare them
3 ¹ = 3
1 ² = 1
3 is greater than 1 and hence p (1) is true.
Let us also show that P(2) is true.
3 ² = 9
2 ² = 4
Hence P(2) is also true.
STEP 2: We now assume that p (k) is true
3 ^k > k ²
Multiply both sides of the above inequality by 3
3 * 3 ^k > 3 * k ²
The left side is equal to 3 ^{k + 1}. For k >, 2, we can write
k ² > 2 k and k ² > 1
We now combine the above inequalities by adding the left hand sides and the right hand sides of the two inequalities
2 k ² > 2 k + 1
We now add k ² to both sides of the above inequality to obtain the inequality
3 k ² > k ² + 2 k + 1
Factor the right side we can write
3 * k ² > (k + 1) ²
If 3 * 3 ^k > 3 * k ² and 3 * k ² > (k + 1) ^{2 then}
3 * 3 ^k > (k + 1) ²
Rewrite the left side as 3 ^{k + 1}
3 ^{k + 1} > (k + 1) ²
Which proves tha P(k + 1) is true

Problem 6

Prove that n ! > 2 ⁿ for n a positive integer greater than or equal to 4. (Note: n! is n factorial and is given by 1 * 2 * ...* (n-1)*n.)
Solution to Problem 6:

Statement P (n) is defined by
n! > 2 ⁿ
STEP 1: We first show that p (4) is true. Let n = 4 and calculate 4 ! and 2 ⁿ and compare them
4! = 24
2 ⁴ = 16
24 is greater than 16 and hence p (4) is true.
STEP 2: We now assume that p (k) is true
k! > 2 ^k
Multiply both sides of the above inequality by k + 1
k! (k + 1)> 2 ^k (k + 1)
The left side is equal to (k + 1)!. For k >, 4, we can write
k + 1 > 2
Multiply both sides of the above inequality by 2 ^k to obtain
2 ^k (k + 1) > 2 * 2 ^k
The above inequality may be written
2 ^k (k + 1) > 2 ^{k + 1}
We have proved that (k + 1)! > 2 ^k (k + 1) and 2 ^k (k + 1) > 2 ^{k + 1} we can now write
(k + 1)! > 2 ^{k + 1}
We have assumed that statement P(k) is true and proved that statment P(k+1) is also true.

Problem 7

Use mathematical induction to prove De Moivre's theorem
[ R (cos t + i sin t) ] ⁿ = R ⁿ(cos nt + i sin nt)
for n a positive integer.
Solution to Problem 7:

STEP 1: For n = 1
[ R (cos t + i sin t) ] ¹ = R ¹(cos 1*t + i sin 1*t)
It can easily be seen that the two sides are equal.
STEP 2: We now assume that the theorem is true for n = k, hence
[ R (cos t + i sin t) ] ^k = R ^k(cos kt + i sin kt)
Multiply both sides of the above equation by R (cos t + i sin t)
[ R (cos t + i sin t) ] ^k R (cos t + i sin t) = R ^k(cos kt + i sin kt) R (cos t + i sin t)
Rewrite the above as follows
[ R (cos t + i sin t) ] ^{k + 1} = R ^{k + 1} [ (cos kt cos t - sin kt sin t) + i (sin kt cos t + cos kt sin t) ]
Trigonometric identities can be used to write the trigonometric expressions (cos kt cos t - sin kt sin t) and (sin kt cos t + cos kt sin t) as follows
(cos kt cos t - sin kt sin t) = cos(kt + t) = cos(k + 1)t
(sin kt cos t + cos kt sin t) = sin(kt + t) = sin(k + 1)t
Substitute the above into the last equation to obtain
[ R (cos t + i sin t) ] ^{k + 1} = R ^{k + 1} [ cos (k + 1)t + sin(k + 1)t ]
It has been established that the theorem is true for n = 1 and that if it assumed true for n = k it is true for n = k + 1.

More References and links

maths problems with detailed solutions .
Home Page