Mathematical Proof By Induction

Proof by induction is just one type of mathematical proof that follows a main method:

1) BASIS:
Prove the general statement is true for n = 1

2) ASSUMPTION:
Assume the general statement is true for n = k

3) INDUCTIVE:
Show that the general statement is then true for n = k + 1

4) CONCLUSION:
The general statement is then true for all positive integers, n.


And an example question:

(BASE STEP)
Prove by the method of mathematical induction that for n is a set of positive natural numbers:

Sum from r=1 to n; (2r-1) = n^2

n=1; LHS = 2(1)-1 = 1
        RHS = 1^2 = 1
Therefore true for n = 1.

(ASSUMPTION)
Assume that the summation formula is true for n = k;

Sum from r=1 to k (2r-1) = k^2

With n = k + 1, terms the summation formula becomes:

(INDUCTIVE STEP)
Sum from r = 1 to (k+1) of (2r-1) = 1+3+...+(2k-1)+(2k+1)
                                                   
= k^2                 + (2k+1)
=k^2 + 2k + 1
=(k+1)^2

Therefore summation formula is true when n = k + 1

(CONCLUSION)
If the summation formula is true for n = k then it is shown to be true for n = k + 1. As the result is true for n = 1, it is now also true for all n  ≥ 1 and n is a set of positive natural numbers by mathematical induction.

TIPS
When trying to prove the inductive step, a very good idea is to write the formulae out that you have derived^^ i.e. (k^2 + 2k + 1) and then write out the other part of the formula (k^2) but replacing k with the summation i.e. k+1; therefore you get (k+1)^2.
Then it is much easier to prove the formulae as you have (k^2 + 2k + 1) and now it is just a matter of rearranging formulae to get (k+1)^2; which in this case is very easy, but helps a lot when the questions become harder.