Proof by Induction

In my last post I talked a little about logic as it applies to generic statements. Now it’s time to think about more mathematics proofs and different techniques. As part of MS221 there are two proof types that we need to consider: proof by exhaustion and proof by induction. This all lays the foundations for building more and more complex mathematical statements so it’s important to get the basics right.

Firstly, proof by exhaustion. This simply means that we try every possible valid input and check that the result is true. A single false result would disprove our proposition. So let’s consider an example:
$(x+1)(x+1) < 50, x = (1, 2, 3, 4, 5, 6, 7, 8)$

So, to prove (or disprove!) by exhaustion we simply substitute each value of x into the equation and check that the answer is less than 50. For x=1 we have:

$(1 + 1)(1+1) = (2)(2) = 4$

Which is less than 50 and so the proposition holds for x=1. Looking at the other numbers we can see that when x = 2 the result is 9, x=3 the result is 16, x=4 the result is 25, x=5 the result is 36 and at x=6 the result is 49. At x=7 however we get 64, and since 64 > 50, the proposition is false for x=7. We have proved by exhaustion that (x+1)(x+1) is not less than 50 for all x in (1,2,3,4,5,6,7, 8).

A trivial example and this is generally only used where you are looking at a small subset of numbers. Imaging a proof by exhaustion of Fermat’s Last Theorem 😉 It is, however, really useful when you can see that a proposition may not be correct and then all you have to do is prove that a single instance is false to disprove the whole proposition (it was fairly obvious that x=7 would fail in the example above).

In a proof by exhaustion, we’re checking every result to make sure it is true. An alternative in the proof by induction, which is the only sensible way when you are dealing with all positive integers for example, when you cannot exhaust all of the possibilities. In essence, the proof by induction is simple for integers. We check that the proposition holds for the first possible value. If it does, we then assume that it is true for an arbitrary value, k, and attempt to prove that the proposition holds for k+1. If it does then, since we know that it holds for the first term (which we can equate to k), then it must hold for all terms. Let’s look at an example (and since I’m posting this before the relevant TMA is due I’m not going to use any of the examples from that assignment, even if it is the last presentation 🙂 ):

$2^n > 2n$

for every positive integer $n > 2$

Step 1: the initial case. The first positive integer greater than 2 is 3 so we have:

$2^3 > 2*3$

$8 > 6$

which is true and so our proposition holds for n=3. So we now assume that n=k and that the following is true:

$2^k > 2k$

Given our assumption that the equation holds for n=k, we consider n= k+1, the next valid integer after k:

$2^{(k+1)} >2(k+1)$

Remembering our laws of powers we can rewrite the left side as:

$2*2^k$

And since we know that:

$2^k > 2k$ ,
therefore $2*2^k$ must be greater than $2*2k$
$2*2k = 4k$
$2(k+1) = 2k + 2$
Since k must be greater than 2, 4k must be greater than $2k +2$
therefore $2^{(k+1)} >2(k+1)$

Since we know that the proposition holds for the first possible value of n (n=3) and we have proved that given any valid value of n (n=k) then the proposition is true for the next value (n=k+1), the proposition must hold true for all values of n. Hence the dominos, once you’ve knocked the start over, they all fall down.

There are lots of really fun examples of this.

Proof by Induction

Published by

janet

Share this:

Related posts:

Published by

janet