Mathematical Induction

Now we move on to induction, the powerful twin of recursion.

Let \(n\) be a positive integer. Consider the following mathematical statements, each of which involve \(n\):

1. \(2n+7 = 13\)
2. \(3n-5=9\)
3. \(n^2-5n+9=3\)
4. \(8n-3 \lt 48\)
5. \(8n-3 > 0\)
6. \((n+3)(n+2) =n^2+5n+6\)
7. \(n^2 -6n + 13 \ge 0\)

Such statements are called open statements. Open statements can be considered as equations, , statements that are valid for certain values of \(n\). Statement1 is valid only when \(n=3\). Statement2 is never valid, , it has no solutions among the positive integers. Statement3 has exactly two solutions, and Statement4 has six solutions. On the other hand, Statements5, 6 and7 are valid for all positive integers.

At this point, you are probably scratching your head, thinking that this discussion is trivial. But let's consider some statements that are a bit more complex.

1. The sum of the first \(n\) positive integers is \(n(n+1)/2\).

2. The sum of the first \(n\) odd positive integers is \(n^2\).

3. \(n^n \ge n! + 4,000,000,000n2^n\) when \(n\ge 14\).

How can we establish the validity of such statements, provided of course that they are actually true? The starting point for providing an answer is the following property:

With a little thought, you should see that the is logically equivalent to the . If you haven't already done so, now might be a good time to look over on background material.