187 – Quiz 7

Here is quiz 7.

Solutions follow.

Problem 1 asks us to prove that, for all natural numbers n, we have 9+9\times 10+\dots+9\times 10^n=10^{n+1}-1.

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 n for which the identity fails, and therefore (since the set A of naturals for which the identity fails is non-empty) there is a least natural k for which the identity fails. This means several things:

  1. 9+9\times 10+\dots+9\times 10^k\ne 10^{k+1}-1.
  2. If n<k is a natural number, 9+9\times 10+\dots+9\times 10^n=10^{n+1}-1.

We begin by noticing that k\ne 0, because 9=10^1-1, meaning that the identity holds in this case.

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

9+9\times 10+\dots+9\times 10^{k-1}=10^k-1. 

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 9\times 10^k to both sides of the displayed equation. We have

(9+9\times 10+\dots+9\times 10^{k-1})+9\times 10^k=(10^k-1)+9\times 10^k =10\times 10^k-1=10^{k+1}-1.

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 n) 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 n=0. This is indeed the case, since 9=10^1-1.

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

9+9\times 10+\dots+9\times 10^n=10^{n+1}-1.

We need to somehow conclude that also 9+9\times 10+\dots+9\times 10^{n+1}=10^{n+2}-1. To do this, we can start with the identity for n, that we are assuming is true, and add 9\times 10^{n+1} to both sides. We obtain

 (9+9\times 10+\dots+9\times 10^n)+9\times 10^{n+1}=(10^{n+1}-1)+9\times 10^{n+1}.

Now we observe that (10^{n+1}-1)+9\times 10^{n+1}=10\times 10^{n+1}-1=10^{n+2}-1, and we conclude that the identity also holds for n+1, 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 a_0=12 and, in general, a_{n+1}=(3a_n+8)/5 for all naturals n. We are asked to prove that a_n>4 for all n\in{\mathbb N}. 

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 n=0. We have a_0=12, which is obviously larger than 4.

Assuming now that a_n>4, we need to prove that a_{n+1}>4 as well. For this, we use that a_{n+1}=(3a_n+8)/5, from which it follows, using the inductive assumption, that

a_{n+1}>(3\times 4+8)/5=(12+8)/5=20/5=4.

This is what we needed to prove. By induction, we conclude that a_n>4 for all n\in{\mathbb N}.

Remark: One can also prove that induction that a_n>a_{n+1} for all n\in{\mathbb N}, i.e., that the sequence is decreasing. To see this, note that a_1=(3\times a_0+8)/5=(3\times 12+8)/5=44/5=8.8<12=a_0. Assuming that a_n>a_{n+1}, we then have that 3a_n>3a_{n+1}, then 3a_n+8>3a_{n+1}+8, and so (3a_n+8)/5>(3a_{n+1}+8)/5. But this means (using the recursive definition of the sequence) that a_{n+1}>a_{n+2}. 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 \lim_{n\to\infty}a_n. In effect, let L=\lim_{n\to\infty}a_n. Then, of course, we also have L=\lim_{n\to\infty}a_{n+1}. Using the recursive definition of the sequence, we then have L=\lim_{n\to\infty}(3a_n+8)/5=(3L+8)/5. The equality L=(3L+8)/5 quickly gives us that L=4.

As a matter of fact, we can show that if b_0 is any real number, and we define the sequence b_0,b_1,b_2,\dots recursively, by setting b_{n+1}=(3b_n+8)/5 for all n\in{\mathbb N}, then:

  1. If b_0>4, then b_n>4 for all n, and the sequence is decreasing, meaning that b_n>b_{n+1} for all n.
  2. If b_0<4, then b_n<4 for all n, and the sequence is increasing, meaning that b_n<b_{n+1} for all n. 
  3. If b_0=4, then b_n=4 for all n.
  4. In all three cases, \lim_{n\to\infty}b_n=4.

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 n that if a,b\in{\mathbb N} and \max(a,b)=n, then a=b=n. 

The case n=0 holds, because if \max(a,b)=0 and a,b are natural numbers, then in fact a=b=0.

Suppose then that the result holds for n and consider natural numbers a,b with \max(a,b)=n+1. Then \max(a-1,b-1)=n and, by the inductive assumption, it follows that a-1=b-1=n. But then a=b=n+1. \Box

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 a,b are natural numbers, then 0\le a,b. If we are also given that \max(a,b)=0, then we have 0\le a\le 0 and 0\le b\le 0, so indeed a=b=0.

It follows that the flaw must lie somewhere within the inductive case. Now, if \max(a,b)=n+1, then indeed \max(a-1,b-1)=n. Also, if a-1=b-1=n, then also a=b=n+1. And, finally, if it is indeed the case that we can apply the inductive assumption then, from \max(a-1,b-1)=n we are forced to conclude that a-1=b-1=n.

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

If \alpha,\beta\in{\mathbb N} and \max(\alpha,\beta)=n, then \alpha=\beta=n,

And we are using it with \alpha=a-1 and \beta=b-1. Since \max(a-1,b-1)=n, the only place we have left, and thus the place where the problem should reside, is in affirming that a-1,b-1\in{\mathbb N}. 

We see that this is, as expected, a problem, because if a,b\in{\mathbb N} and \max(a,b)=n+1, then we cannot conclude that both a-1,b-1\in{\mathbb N} as well. Of course, one of a-1,b-1 equals n and n\in{\mathbb N} but, for all we know, we could have a=0 and b=n+1. Then a-1=-1\notin{\mathbb N}, and the inductive assumption does not apply to a-1,b-1 since they are not both natural numbers.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: