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 + 2 2 + 3 2 + ... + n 2 = n (n + 1) (2n + 1)/ 6

For all positive integers n.

Solution to Problem 2:

  • Statement P (n) is defined by

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

  • STEP 1: We first show that p (1) is true.

    Left Side = 1 2 = 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 + 2 2 + 3 2 + ... + k 2 = k (k + 1) (2k + 1)/ 6

  • and show that p (k + 1) is true by adding (k + 1) 2 to both sides of the above statement

    1 2 + 2 2 + 3 2 + ... + k 2 + (k + 1) 2 = k (k + 1) (2k + 1)/ 6 + (k + 1) 2

  • 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 2 + 7k + 6 ] /6

  • Now factor 2k 2 + 7k + 6.

    = (k + 1) [ (k + 2) (2k + 3) ] /6

  • We have started from the statement P(k) and have shown that

    1 2 + 2 2 + 3 2 + ... + k 2 + (k + 1) 2 = (k + 1) [ (k + 2) (2k + 3) ] /6

  • Which is the statement P(k + 1).


Problem 3:

Use mathematical induction to prove that

1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4

for all positive integers n.

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).


Problem 4:

Prove that for any positive integer number n , n 3 + 2 n is divisible by 3

Solution to Problem 4:

  • 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.


Problem 5:

Prove that 3 n > n 2 for n = 1, n = 2 and use the mathematical induction to prove that 3 n > n 2 for n a positive integer greater than 2.

Solution to Problem 5:

  • 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


Problem 6:

Prove that n ! > 2 n 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 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.


Problem 7:

Use mathematical induction to prove De Moivre's theorem

[ R (cos t + i sin t) ] n = R n(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) ] 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.

More math problems with detailed solutions in this site.

privacy policy