Number theory question - binary trees

[miren324]

Here's the question.
Starting with an integer a≥2, we write on its left, below it, the number a+1, and on its right, below it, the number a^2, and obtain four numbers, to which we continue the process. We thus obtain a binary tree, whose root is a. Prove that the numbers in every line of the tree are all different. Hint: Assume that there is a first line with two equal entries and derive a contradiction.

So basically, we have a tree that looks like (ignore the dots; it was the only way I could figure out how to space everything out correctly):

......a
...a+1.....a^2
a+2...(a+1)^2...a^2+1...(a^2)^2

and so on.


Attempt at solution:
We can assume that a=2, because if we prove for a=2, then we've proven for all integers a≥2 since a=3, a=4, and so on produce sub-trees of a=2.
If there exist lines that have at least two entries that are equal, then there is a first such line. Let's assume that line k is the first line. Obviously if two entries are equal and they are both of the form b+1 or both of the form b^2, then their roots would be equal, contradicting the assumption that k is the first line with equal entries. Therefore, if two entries are equal, one is a square and the other is a +1.

This is where I'm stuck. Since the two entries are equal, then we have a number with two different roots: x^2's root is x, and it's other root (from a different part of the tree, but on the same line) is x^2-1, so we have at some point in the tree (this time the dots represent extra data I'm not including, so there may be numbers between the dots):

... x ...... x^2-1 ...... line k-1
... x+1 x^2 ... x^2 (x^2-1)^2 .... line k

I'm not sure where to go from here. According to the hint I need to find a contradiction, and I'm sure that contradiction is to the assumption that k is the first line with equal entries, so we need to somehow show that if x^2=x^2 in line k, then x=x^2-1, or possibly some other entries in line k-1 are equal. I'm just not seeing how to do this.

Also, I've been told by my teacher, and have seen in previous homeworks, that once you figure out exactly what to do for the proof of these problems, the proof is actually rather short and simple. It's usually only a few lines long, which makes this even more frustrating that I can't find out exactly what I should be doing with these numbers.

Any help would be greatly appreciated.

 

[eumyang]

So basically, we have a tree that looks like (ignore the dots; it was the only way I could figure out how to space everything out correctly):

......a
...a+1.....a^2
a+2...(a+1)^2...a^2+1...(a^2)^2

and so on.

Use the CODE tags to make text space the way you want, like this:

                  a
                  |
       +----------+------------+
       |                       |
      a+1                     a^2
       |                       |
 +-----+-------+          +----+-----+
 |             |          |          |
a+2         (a+1)^2     a^2+1       a^4

 

[Dick]

Here's one way to think about it. Imagine you have two equal numbers in a row. Now imagine the smallest subtree that contains them both. What are the possibilities for the numbers in terms of the number that's the root of that smallest subtree?

 

[miren324]

Not sure exactly where you're headed with that. For all I know the two separate entries for x^2 could be on exact opposite sides, meaning that the smallest sub-tree has 2 as it's root.

 

[Hurkyl]

or possibly some other entries in line k-1 are equal.

You could go back more than one line...


Incidentally, not every proof that starts with "assume there is a smallest counterexample" proceeds by demonstrating an even smaller counterexample would exist.

 

[Dick]

Not sure exactly where you're headed with that. For all I know the two separate entries for x^2 could be on exact opposite sides, meaning that the smallest sub-tree has 2 as it's root.

2 is a fine root. The point is that the two equal numbers must be in the two pairs numbers at the outer ends of the subtree. I can name some pairings of those numbers that can't be equal. Can you show none of them can be equal?