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

^{2}, 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

^{2}:

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

^{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.}

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

^{2}+2n+1

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

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

^{2}

Which means that our original assumption was correct! Ergo the sum of the first n odd numbers does equal to n

^{2 }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 InductionPrinciple 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

^{2}our assumption is true for P(1), 1 = 1

^{2}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.

But why is this so? I understand the proof, and I computed it on my own, but do we have any feel for why this would be so? What does this tell us about the numbers?

ReplyDelete