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
Solution to Problem 3:
Statement P (n) is defined by
1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4
STEP 1: We first show that p (1) is true.
Left Side = 1 3 = 1
Right Side = 1 2 (1 + 1) 2 / 4 = 1
hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 3 + 2 3 + 3 3 + ... + k 3 = k 2 (k + 1) 2 / 4
add (k + 1) 3 to both sides
1 3 + 2 3 + 3 3 + ... + k 3 + (k + 1) 3 = k 2 (k + 1) 2 / 4 + (k + 1) 3
factor (k + 1) 2 on the right side
= (k + 1) 2 [ k 2 / 4 + (k + 1) ]
set to common denominator and group
= (k + 1) 2 [ k 2 + 4 k + 4 ] / 4
= (k + 1) 2 [ (k + 2) 2 ] / 4
We have started from the statement P(k) and have shown that
1 3 + 2 3 + 3 3 + ... + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4
Which is the statement P(k + 1).
Statement P (n) is defined by
n 3 + 2 n is divisible by 3
STEP 1: We first show that p (1) is true. Let n = 1 and calculate n 3 + 2n
1 3 + 2(1) = 3
3 is divisible by 3
hence p (1) is true.
STEP 2: We now assume that p (k) is true
k 3 + 2 k is divisible by 3
is equivalent to
k 3 + 2 k = 3 M , where M is a positive integer.
We now consider the algebraic expression (k + 1) 3 + 2 (k + 1); expand it and group like terms
(k + 1) 3 + 2 (k + 1) = k 3 + 3 k 2 + 5 k + 3
= [ k 3 + 2 k] + [3 k 2 + 3 k + 3]
= 3 M + 3 [ k 2 + k + 1 ] = 3 [ M + k 2 + k + 1 ]
Hence (k + 1) 3 + 2 (k + 1) is also divisible by 3 and therefore statement P(k + 1) is true.
Statement P (n) is defined by
3 n > n 2
STEP 1: We first show that p (1) is true. Let n = 1 and calculate 3 1 and 1 2 and compare them
3 1 = 3
1 2 = 1
3 is greater than 1 and hence p (1) is true.
Let us also show that P(2) is true.
3 2 = 9
2 2 = 4
Hence P(2) is also true.
STEP 2: We now assume that p (k) is true
3 k > k 2
Multiply both sides of the above inequality by 3
3 * 3 k > 3 * k 2
The left side is equal to 3 k + 1. For k >, 2, we can write
k 2 > 2 k and k 2 > 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 > 2 k + 1
We now add k 2 to both sides of the above inequality to obtain the inequality
3 k 2 > k 2 + 2 k + 1
Factor the right side we can write
3 * k 2 > (k + 1) 2
If 3 * 3 k > 3 * k 2 and 3 * k 2 > (k + 1) 2 then
3 * 3 k > (k + 1) 2
Rewrite the left side as 3 k + 1
3 k + 1 > (k + 1) 2
Which proves tha P(k + 1) is true
Statement P (n) is defined by
n! > 2 n
STEP 1: We first show that p (4) is true. Let n = 4 and calculate 4 ! and 2 n and compare them
4! = 24
2 4 = 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.
STEP 1: For n = 1
[ R (cos t + i sin t) ] 1 = R 1(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.