Proof by Induction: Sum of Odd Numbers

I will introduce an integral part of mathematics in this blog post, proof by induction. It is fundamental to many proofs and is a pretty simple concept to grasp, I will demonstrate how this proof works with a simple example.

The first basis of proving by induction requires some intelligent intuition to our problem. This means that we look at the pattern of what is happening and try to prove this for all values. For the sum of square numbers this goes:

1 = 1
1+3 = 4
1+3+5 = 9
1+3+5+7 = 16

You may have noticed from this that the sum the answers is always a square number. The sum of the first n odd numbers appears to always equal n², but it just appears that way for the examples that we have given, we do not know that is true for all values, yet.

So our assumption is the sum of the first n odd numbers equals to n²:
1+3+5+...+(2n-1) = n<sup>2

This is our assumption, but if we can prove that n+1 odd numbers equals to (n+1)2 then that means it will hold true for the sums of any number of odd numbers. To begin to check this we add n+1th odd number onto both sides of our assumption.</sup>

1+3+5+...+(2n-1)+(2n+1) = n²+2n+1

As you can see the right side does factorise to give:

1+3+5+...+(2n-1)+(2n+1) = (n+1)²

Which means that our original assumption was correct! Ergo the sum of the first n odd numbers does equal to n² formally in mathematical notation this is:

And that is it for an example of how you use the proof by induction, now it just needs to be put in terms that are applicable for all problems.

Principle of Mathematical Induction
If for each positive integer n we have a statement P(n). If we prove the following two things then the statement is true:
a.) P(1) is true.
b.) For all n, if P(n) is true then P(n+1) is also true. This then means that P(n) is true for all positive integers n.

If that is pretty hard to compute look back to our example, our assumed statement is that P(n) = n² our assumption is true for P(1), 1 = 1² and we then proved that assuming P(n) is true that P(n+1) is also true. Therefore if P(1) is true, then P(2) is true too, etc.

Stay tuned for my future blog posts where I will utilise mathematical induction to find general formulas or proofs to many things.