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

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"?

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.

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?