From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: binary tree
Date: 23 Oct 1995 21:09:04 GMT

In article <463ck7$ck@news.asu.edu>,  <ass123@imap1.asu.edu> wrote:
>let a be a positive integer, a => 2. Construct a binary tree starting 
>from a as the root, and writing to the left a + 1, and to the right a^2.  
>Continue in this way indefinitely.  Show that at every level of this 
>tree, all numbers are different.

Let  S  be the operator  S(x)=x^2  and  T  the operator  T(x)=x+1.
Then the question is whether there can be two distinct words in  S  and  T
of equal lengths, having  w1(a)=w2(a)  for some  a >= 2.
The answer is no.

Consider a counterexample involving  w1  and  w2  of minimal length; then
the leftmost operators in w1 and w2 must be different. Write, say,
w1 = S w1'  and  w2= T^i S w2' for some positive integer  i<n  and some other
words  w1' and w2', possibly empty.  (There is the possibility that  w2 = T^n,
that is, that no  S  appears in  w2, but that case is easily dispensed with
since  T^n(a)  will be less than every other output  w(a). See below for
more details on magnitude.)

Now the equation w1(a)=w2(a) unscrambles to be
	(w1'(a))^2 = i + (w2'(a))^2, 
which we rewrite as
	(w1'(a)+w2'(a)) * (w1'(a)-w2'(a)) = i
Since  i  is nonzero, the factors are nonzero. Of course, each word
evaluates to an integer, so the second factor is at least 1 in magnitude,
forcing the first factor to be at most  i.

On the other hand, for all x>1 we have  S(x) > T(x)=x+1 > 1  which
allows an inductive proof that  w(a) >= a+n  (where  n  is the length of
the word  w). In particular, w2'(a) >= a+n-2 and w1'(a) >= a+n-1-i, so that
the first factor above is at least 2a+2n-3-i >= 2n+1-i, which is larger 
than  i<n.

Thus there is no minimal counterexample and the conjecture is proven.


I should comment that my first thought was to show the distinctness  of
the outputs by showing a difference in magnitude, at least for large  a.
Here's what one can show. Declare a total order on the words of length  n
as follows:  w1 < w2  iff  w1  has fewer  S's  than  w2, or they have
the same number of  S's  but  w1  precedes  w2  lexicographically
(reading from right to left, with  S  preceding  T). For example, here
are the 2^4 words with  n=4  arranged from least to greatest:

TTTT TTTS TTST TSTT STTT TTSS TSTS STTS TSST STST SSTT TSSS STSS SSTS SSST SSSS

Then one can show

Theorem: if  w1 < w2  in the sense above then  w1(a) < w2(a) for all 
sufficiently large  a. (For example,  a > n/2  will do.)

Proof: by induction on the length  n  of the words. If  n=1, this is trivial.
Assuming it's true for words of length  n-1, we can compare the words of
length  n. It suffices to show  w1(a) < w2(a) for each adjoining pair of
words  w1 < w2  in the ordered list.

If  w1 and  w2  have any common initial or final terms, then the fact that
w1(a)<w2(a)  follows by induction. (Actually if  w1=w1' S and w2=w2' S and
we know  w1'(a) < w2'(a)  for all a >= a0, then we have  w1(a)<w2(a) for
all  a >= sqrt(a0); likewise if  w1  and  w2  have a final  T  in common, 
the bound for the set of valid  a  is _lower_ than for  w1' and w2').

If instead  w1  and  w2  have distinct final terms, we distinguish two
cases, according to whether or not they have the same number of  S's. First,
in the case that they do, then the statement  w1 < w2  implies  w1  ends in
S, w2 in T. Moreover, the statemnt that w1 and w2 are _adjacent_ in the
ordering pins them down much further: for some  i  and  j=n-i-1, we have
	w1=S^i T^j S,    w2=T^(j-1) S^(i+1) T
To see that  w1(a) < w2(a)  we need to see if
	((a^2)+j)^(2^i) < (a+1)^(2^(i+1)) + j-1
which we write as a difference of two  2^i-th powers:
	1-j < x^(2^i) - y^(2^i),   x=(a+1)^2, y=a^2+j
Well, this inequality certainly holds if the right side is positive,
that is, if  x > y. But this holds if  (a+1)^2 > a^2 + j, i.e. if
a>(j-1)/2. To cover all such cases we need only assume  a > (n-3)/2.

Finally we assume  w1 and  w2  are adjacent words with different numbers
of  S's. This means that for some  i  and  j  (summing to n)  we have
w1=S^i T^j, w2=T^(j-1) S^(i+1). As in the previous paragraph, we write 
the inequality to be demonstrated as
	1-j < x^(2^i) - y^(2^i)   x=a^2, y=a+j
and we observe this holds if  x>y, which is certainly true if
a^2-a-(n-1) > 0, e.g. if  a > sqrt(n)+1.

This completes the proof that  w1 < w2  =>  w1(a) < w2(a) for almost all  a.
In particular, all  w(a)  will be unequal, except possibly for the
smallest values of  a.  But this line of reasoning is insufficient to handle
the general case ( n >> a ),  so the first argument in this post is needed.

dave