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

Home Page