Just because the sun has risen each and every day for as long as anybody can remember does not entail that it will definitely rise tomorrow. There is always the least chance that something will be amiss, and that some unforeseen event will disrupt the otherwise predictable cycle of the earth rotating on its axis. In short, the world is an unpredictable place. In the world of mathematics, however, certainty is more readily available. In fact, there are a number of techniques that may be employed to prove the certainty of different sorts mathematical of facts, and induction is one of these.
Induction provides away to prove the mathematical equivalent of propositions like "the sun will rise tomorrow, forever and ever". Such an equivalent is present in the proposition "the sum of the integers 1 through n is equal to n(n+1)/2". In this lesson, we will use induction to prove that fact. But first, what is induction?
At the heart of mathematical induction rests a simple intuition:
A more precise definition of the principle of induction can be stated in terms of propositions about the natural numbers. A proposition P(i) about the natural numbers is a statement that for is either true or false each natural number i. For instance, P(i) could be "i is an even number". In that case P(4) would be true, but P(7) would be false. In these terms, induction is usually defined in the following manner.
If P(1) is true, and if whenever P(i) is true, we can infer the truth of P(i+1), then P(i) is true for all natural numbers i.
This makes sense because, if P(1) is true, then we know we can infer the truth of P(1+1) = P(2), which in turn means we can infer the truth of P(2+1) = P(3), and so on into infinity. Hence, we arrive at the most important fact about induction: if we can count, we probably use induction!
In order to make use of induction, a fact about the natural numbers is required to be our proposition P(n). Mentioned above was the statement "the sum of numbers 1 through n is equal to n(n+1)/2", this will serve as our our example.
Next, we must make sure that we're starting on solid ground by answering the question "is P(1) true?" This is often called checking the base case.
So P(1) is true! It checks out because the sum of all numbers from 1 to 1 (which is, of course, just 1) is equal to 1(1+1)/2 = 1.
Now we suppose that P(m) is true for some arbitrary m. We want to see if we can deduce the truth of P(m+1) using only the fact that P(m) is true. To accomplish this, we will see if we can get the sum of the numbers from 1 to m+1 to look like (m+1)((m+1) + 1)/2.
Because we assumed that the sum of numbers from 1 to m was equal to m(m+1)/2, we can just substitute that m(m+1)/2 in place of that sum. Lets move on.
Hence, because P(1) is true, and because we have shown that whenever P(m) is true then P(m+1) must also be true, then we may conclude that P(n) is true for all natural numbers n!
