# Recursive Trees (from GED)

1. Aug 2, 2006

### dobry_den

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

2. Aug 2, 2006

### 3trQN

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

3. Aug 2, 2006

### dobry_den

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 (Text):

(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.

4. Jul 8, 2009

### torteloni

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?