## 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 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 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.