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 * ...* (n1)*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.