Recursive Trees (from GED)

**dobry_den** · Aug2-06, 12:32 PM

In chapter five of Douglas Hofstadter's book Goedel, Escher, Bach, the author poses a question about recursively-defined trees:

[...]suppose you flip Diagram G around as if in a mirror, and label the nodes of the new tree so they increase from left to right. Can you find a recursive algebraic definition for this "flip-tree"?

I've been trying to solve it today, and the only solution I came up with is:

G(n) = (n+1) - G(G(n-1)+1) for n>4
G(O) = 0, G(1) = 1, G(2) = 2, G(3) = 3, G(4) = 3 (hope i remember it well),

which is apparently not as elegant as the original definition. Has anyone of you come up with a better solution? Or is there any general method (procedure) how to transform recursive algebraic definition of trees into recursive algebraic definitions of "flip-trees"?

**3trQN** · Aug2-06, 01:16 PM

Doesnt it have something to do with odd and even numbers, a bit like the trigonometric functions of the tayor series?

**dobry_den** · Aug2-06, 01:48 PM

Originally Posted by 3trQN

Doesnt it have something to do with odd and even numbers, a bit like the trigonometric functions of the tayor series?

I'm not sure about that... I'll try to state the whole problem:

Having a recursive algebraic definition of a function F(n), one can construct a tree by placing n-nodes above F(n)-nodes:

Code:

       
                         (4)        (5)
                          |          |
                          ----(2)-----           (3)
                               |                  |
                               --------(1)---------

For this particular tree, these equations hold:

G(2)=1
G(3)=1
G(4)=2
G(5)=2

The tree in the book is described by the equation:

G(n) = n - G(G(n-1)) for n>0
G(0) = 0

And the problem is following: imagine you flip the tree around as if in a mirror and relabel all the nodes so they increase from left to right. What would be the recursive algebraic definition for this mirrored tree?

The solution I came up with is mentioned in my previous post... But apparently it lacks the original elegance - in order to be suitable for the tree, it has to be given five initial values. The original "unmirrored" tree used only one predefined value.

**torteloni** · Jul8-09, 08:11 AM

I came to the same result this day (actually I gave even more initial values, but my recurrence relation was the same). But I have the same two problems with it: The solution is really unhandy and everything but elegant... Ant at second it still is only an assumption. Unfortunately I have absolutely no clue how it could be shown that this recurrence relation fits to the tree (and it is not even easy to falsify: Calculating high G-flip(n) is okay but having a look at the 2000th level of this weird tree is not that easy...).

So now my question: Were there any new discoveries in the past few years? Is there any elegant form now or does anyone of you have an idea?