187 – Quiz 7

Here is quiz 7.

Solutions follow.

Problem 1 asks us to prove that, for all natural numbers we have

There are several ways of showing this. I present two proofs, one using the well-ordering principle (least counterexample), and the other arguing by induction.

Proof 1: Using the well-ordering principle, one proceeds as follows: Suppose the result is false. This means that there is a natural for which the identity fails, and therefore (since the set of naturals for which the identity fails is non-empty) there is a least natural for which the identity fails. This means several things:

1. 
2. If is a natural number,

We begin by noticing that because meaning that the identity holds in this case.

It follows that is also a natural number. By item 2, we then have that

 

The plan is now to somehow transform this equality into the equality that item 1 claims must fail. To do this, the most direct route seems to be to add to both sides of the displayed equation. We have

We have indeed shown that item 1 is false. This is a contradiction, and we conclude that our assumption (that the identity fails for some natural ) is false, meaning of course that the identity holds for all natural numbers, as we wanted to prove.

Proof 2: Using induction, one argues as follows: First, we show that the identity is true when This is indeed the case, since

Now we assume that the identity holds for some number meaning that

We need to somehow conclude that also To do this, we can start with the identity for that we are assuming is true, and add to both sides. We obtain

 

Now we observe that and we conclude that the identity also holds for as we wanted to show.

By induction, we conclude that the identity holds for all natural numbers.

[Note that both proofs are very similar, as was to be expected.]

Problem 2 starts by defining a sequence by recursion: We set and, in general, for all naturals We are asked to prove that for all  

Once again, one can argue by either the well-ordering principle, or induction. I present here a proof using induction. First, we consider the case We have which is obviously larger than

Assuming now that we need to prove that as well. For this, we use that from which it follows, using the inductive assumption, that

This is what we needed to prove. By induction, we conclude that for all

Remark: One can also prove that induction that for all i.e., that the sequence is decreasing. To see this, note that Assuming that we then have that then and so But this means (using the recursive definition of the sequence) that By induction, the sequence is decreasing.

A fundamental result in calculus is that a decreasing sequence that is bounded below must converge. We can now easily compute In effect, let Then, of course, we also have Using the recursive definition of the sequence, we then have The equality quickly gives us that

As a matter of fact, we can show that if is any real number, and we define the sequence recursively, by setting for all then:

1. If then for all and the sequence is decreasing, meaning that for all
2. If then for all and the sequence is increasing, meaning that for all  
3. If then for all
4. In all three cases, 

Though the example presented here is simple, this technique of computing limits of sequences by studying their behavior using induction, is actually very useful in higher calculus (mathematical analysis).

Problem 3 asks us to identify the flaw in the following wrong argument:

Theorem. All natural numbers are equal.

Proof. We argue by induction on that if and then  

The case holds, because if and are natural numbers, then in fact

Suppose then that the result holds for and consider natural numbers with Then and, by the inductive assumption, it follows that But then  

The argument is presented as a proof by induction, with the base case and the inductive case indicated. If indeed both cases are argued correctly, the conclusion will follow. This means that the flaw is either in the proof of the base case or of the inductive case.

The base case, however, is proved correctly: If are natural numbers, then If we are also given that then we have and so indeed

It follows that the flaw must lie somewhere within the inductive case. Now, if then indeed Also, if then also And, finally, if it is indeed the case that we can apply the inductive assumption then, from we are forced to conclude that

It follows that the flaw is in assuming that the inductive assumption applies. Recall that the inductive assumption is:

If and then

And we are using it with and Since the only place we have left, and thus the place where the problem should reside, is in affirming that  

We see that this is, as expected, a problem, because if and then we cannot conclude that both as well. Of course, one of equals and but, for all we know, we could have and Then and the inductive assumption does not apply to since they are not both natural numbers.

Advertisement