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