From: Jacob Fugal <lukfugl@...>
Date: 2006-09-02T07:39:40+09:00
Subject: Re: Happy Numbers (#93)

On 9/1/06, Jacob Fugal <lukfugl@gmail.com> wrote:
> Now, take any i >= 4. For all x in Qi, x' <= Mi' = 81 * i. But 81 * i
> < 10^(i-1) (see below), so 81 * i <= M(i-1), and x' <= M(i-1) for all
> x in Qi. But since x > M(i-1) by our choice, we know that x' < x. This
> is true for *all* x > 999.

And here's the "below" referred to (I forgot it earlier). :)

Remember that i >= 4. Let's take i = 4 as a basis case.

81 * 4 = 324 < 1000 = 10^(4-1)

Now, assume the hypothesis for some i >= 4. We will prove the
hypothesis continues to hold for j = i + 1.

Since 1/9 < i; 81 < 9 * 81 * i.
Adding 81 * i to both sides of that inequality we get:
81 * j < 10 * 81 * i

From the other side, we can start with the inequality for i (81 * i <
10^(i-1)) and multiply both sides by 10 to get:
10 * 81 * i < 10^(j-1)

Combining those two inequalities, we have: 81 * j < 10^(j-1).

Isn't induction great? :)

Jacob Fugal