I'm reading "Godel, Escher, Bach" and note that the author claims there are simple diagrams to functions defined:
M(n) = n - F(M(n-1)), n > 0,
F(n) = n - M(F(n-1)), n > 0,
F(0) = 1,
M(0) = 0.
I think I have the answer but it's not as elegant as I expect. The diagrams here for those unfamiliar with the problem involve discovering a recursive structure to the tree graph that forms with a low number as the root. Each node has as its children all the values of n which produce that node by the function.
Here is my solution, upside-down (root at the top) for ease of reproducing it here:
M is (starting from 3):
N is:Code:| --O-- | | N M'
M' is:Code:| O | N
and F is simply (starting from 2):Code:| --O-- | | G M'
If you don't have the book, G is:Code:| --O-- | | O F | G
G is the diagram for G(n) = n - G(G(n-1)), which yields the Fibonacci sequence.Code:| --O-- | | O G | G
N is a rising tower of non-recursive nodes that forms the Fibonacci sequence exactly. In F, the same sequence is seen along the right side (when you remain in F without switching to G).
1) Have I erred?
2) If not, is there a more elegant approach?
Thanks for your eyes!