The Universe of Disco

Tue, 20 Jun 2006

484848 is excellent
Brad Murray wrote to request a proof that the number 4848...4848 is excellent:

So, are all concatenations of odd numbers of "48" excellent? I demand a proof!

So okay, it wasn't a request. I have been given no choice but to comply. I hear and I obey, O mighty one!

First let's define the items we're talking about:

a₀ = 4, a_n+1 = 100a_n + 84, so that the a_n are 4, 484, 48484, etc.
Similarly, b₀ = 8, b_n+1 = 100b_n + 48, so that the b_n are 8, 848, 84848, etc.
Similarly, c₀ = 48, c_n+1 = 10000c_n + 4848, so that the c_n are 48, 484848, 4848484848, etc.

I now assert that c_n is the concatenation of a_n and b_n, by one or more of the following arguments:

It's obvious, or even if not,
it follows from an easy inductive proof, which
is left as an exercise for the reader.

(This sounds like a joke, but it isn't; I honestly expect people will find it obvious, or that even if not they will agree that it should follow from an easy induction.)

In order to show that c_n is excellent, it then suffices to show that c_n = b_n² - a_n² for all n.

First we'll prove the following lemma: for all n, 4b_n - 7a_n = 4. This follows easily by induction. For n=0, we have 4·8 - 7·4 = 32 - 28 = 4. Now suppose the lemma is proved for n=i; we want to show that it is true for n=i+1. That is, we want to calculate:

4b_i+1 - 7a_i+1 =

4(100b_i+48) - 7(100a_i+84) =

400b_i + 192 - 700a_i - 588 =

400b_i + 700a_i + 192 - 588 =

100(4b_i - 7a_i) - 396 =

100·4 - 396 =

4

And we are done.

Now the main theorem, again by induction. We want to show that:

b_n² - a_n² = c_n

for all n. For n=0 this is trivial, since we have 8² - 4² = 64 - 16 = 48. Now suppose we know it is true for n=i; we will show that it is true for n = i+1 as well:

b_i+1² - a_i+1² =

(100b_i + 48)² - (100a_i + 84)² =

10000b_i² + 9600b_i + 2304 - 10000a_i² - 16800a_i - 7056 =

10000(b_i² - a_i²) + 2400(4b_i - 7a_i) + 2304 - 7056 =

10000c_i + 2400(4b_i - 7a_i) - 4752 =

10000c_i + 2400·4 - 4752 =

10000c_i + 4848 =

c_i+1

Q.E.D.

I may have more to say about this later. I have a half-written article that complains about homework questions of the form "Solve problem X using technique Y," where Y is something like induction. The article was inspired by a particularly odious problem of this type:

if n + 1 balls are put inside n boxes, then at least one box will contain more than one ball. prove this principle by induction.

Nobody in his right mind would prove this principle by induction. You prove it by pointing out that if the conclusion were to fail, no box would have more than one ball; since there are n boxes, each of which has no more than one ball, then there are no more than n balls, and this contradicts the hypothesis. Using induction is idiotic.

A student faced with this kind of question will conclude (correctly) that he or she is being forced to jump through a pointless hoop, and may conclude (incorrectly) that induction is useless. And students are frequently confused by pointless applications of principles. People learn better when they understand why things are happening; when students feel that they don't understand the point of what is being done, they feel that they don't understand the mechanics either.

In the real world—by which I mean what real scientists, mathematicians, and engineers do, in addition to what people in the grocery store do—I am excluding only homework assignments—we almost never get a problem of the form "solve X using technique Y". Problems we face in the real world always have the form "solve X, by hook or by crook." The closest we ever see to a prescribed technique are mere suggestions like "Well, Y might work here, so you could try that."

Questions that prescribe techniques are either lazy pedagogy or bad curriculum design. If technique Y—say, induction—is a useful technique, then it is because there is some problem X such that Y is superior to all other techniques for solving X. If all such X are outside the scope of the class, then Y is outside the scope of the class too. If, on the other hand, there is some X that is in the scope of the class, it is the instructor's job to find it and present it to the students, as an instructive example. To fail in this, and to make up a contrived and irrelevant problem in place of X, is a failure of the instructor's principal duty, which is to illustrate the subject matter by realistic and relevant examples.

For the theorem above about 484848, induction is clearly a good way to solve it; to solve the problem by direct calculation is painful.

There are other things to learn from the demonstration above. It serves as a wonderful example of what is wrong with standard mathematical style for writing up proofs. A student seeing this proof might well ask "where the heck did you get that lemma about 4b - 7a = 4? Is that something you knew from before? Did you just guess? Was it in the book somewhere?" But no, I did not guess, I did not know that before, and I did not get it from the book.

The answer is that I did the main demonstration first, starting with b_i² - a_i² and trying to get from there to c_i by using algebraic manipulations and the definitions of a, b, and c. And just when everything seemed to be going along well, I got stuck. I had:

10000c_i + 2400(4b_i - 7a_i) - 4752

This looked something like what I was trying to manufacture, which was:

10000c_i + 4848

but it was not quite right. The 10000c_i part was fine, but instead of 2400(4b_i - 7a_i) - 4752 I needed 4848.

So if it was going to work, I needed to have:

2400(4b_i - 7a_i) - 4752 = 4848

or equivalently:

2400(4b_i - 7a_i) = 9600

which is equivalent to:

4b_i - 7a_i = 4.

So I had better have 4b_i - 7a_i = 4; if this turns out false, the whole thing falls apart.

But a quick check of a couple of examples shows that 4b_i - 7a_i = 4 does work, at least for i=0 and 1, so maybe it would worth trying to prove in the general case. And indeed, the proof went through fine, and I won.

But in the presentation of the proof, everything is backwards: I pull the mystery lemma out of my ass at the beginning for no apparent reason, and then later on it happens to be what what I need at the crucial moment. Almost as if I knew beforehand what was going to happen!

There are a lot of things wrong with mathematics pedagogy, and those were two of them: artifically prescribed techniques to solve homework problems, and the ass-extraction of lemmas backwards in time.

[Other articles in category /math] permanent link