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>, 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 i1 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/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)= a0, then we have w1(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