## Help me find the recursive formula

I'm reading Godel, Escher Bach: An Eternal Golden Braid by Hofstader. He describes a geometric shape formed by writing n in a circle and then writing G(n) in a circle below it and connecting the two circles with a line. It ends up looking sort of like a tree. Try it yourself if you want.

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

You start with n=2 in a circle to make the tree. Now suppose you flipped the tree as if in a mirror and renumbered the circles increasing from left to right, starting with the lowest circles. The challenge is to find an algebraic definition for this new tree. If you place F(n) beneath n then the equations you get are:

F(2)=1
F(3)=2
F(4)=3
F(5)=3
F(6)=4
F(7)=5
F(8)=5
F(9)=6
F(10)=6
F(11)=7
F(12)=8
F(13)=8
F(14)=9
F(15)=10
F(16)=10
F(17)=11
F(18)=11
F(19)=12
F(20)=13
F(21)=13

If you can figure out F(n) please point me in the right direction.

 Recognitions: Homework Help Science Advisor Can you explain the process again? I've computed some values for G: G(0) = 0 G(1) = 1 - G(G(0)) = 1 - G(0) = 1 - 0 = 1 G(2) = 2 - G(G(1)) = 2 - G(1) = 2 - 1 = 1 G(3) = 2 G(4) = 3 G(5) = 3 G(6) = 4 G(7) = 4 G(8) = 5 G(9) = 6 G(10) = 6 G(11) = 7 G(12) = 8 G(13) = 8 G(14) = 14 - G(G(13)) = 14 - G(8) = 14 - 5 = 9 Starting with n=2, then I think the tree would look like this: (2) | | (1) | | (1) | | (1) | | . . . This will form an infinite tree, but not a very interesting one. I'm not sure what mirror you're talking about, but since you talk about the new image going left to right, maybe you mean a 45 degree mirror that makes the tree horizontal instead of vertical. Maybe you can upload a .jpg of what this thing is supposed to look like. Anyways, try playing around with a definition for F that's similar to the definition for G. From your description, however, I can't tell what F is even referring to, let alone find a pattern. I'm trying out F(n) = n+1 - F(F(n-1)+1) and it has worked for F(4) to F(15). It fails for F(3) and F(16), which is annoying since it works for all the ones in between! F(n) = n + 1 - F(F(n-1)+1) F(4) = 5 - F(F(3)+1) = 5 - F(3) = 5 - 2 = 3 X F(5) = 6 - F(F(4)+1) = 6 - F(4) = 6 - 3 = 3 F(6) = 7 - F(F(5)+1) = 7 - 3 = 4 F(7) = 8 - F(F(6)+1) = 5 F(8) = 9 - F(F(7)+1) = 9 - F(4) = 5 F(9) = 10 - F(F(8)+1) = 10 - 4 = 6 F(10) = 11 - F(F(9)+1) = 11 - 5 = 6 F(11) = 12 - 5 = 7 F(12) = 13 - 5 = 8 F(13) = 14 - 6 = 8 F(14) = 15 - 6 = 9 F(15) = 16 - 6 = 10 F(16) = 17 - F(F(14)+1) = 17 - F(9+1) = 17 - F(10) = 17 - 6 = 11 X
 Recognitions: Homework Help Science Advisor Define H(n) = n - F(n) F(2)=1, H(2) = 1 F(3)=2, H(3) = 1 F(4)=3, H(4) = 1 F(5)=3, H(5) = 2 F(6)=4, H(6) = 2 F(7)=5, H(7) = 2 F(8)=5, H(8) = 3 F(9)=6, H(9) = 3 F(10)=6, H(10) = 4 F(11)=7, H(11) = 4 F(12)=8, H(12) = 4 F(13)=8, H(13) = 5 F(14)=9, H(14) = 5 F(15)=10, H(15) = 5 F(16)=10, H(16) = 6 F(17)=11, H(17) = 6 F(18)=11, H(18) = 7 F(19)=12, H(19) = 7 F(20)=13, H(20) = 7 F(21)=13, H(21) = 8 It appears so far that there is a pattern 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, ... in the way that H values are grouped together. I(n) = n - G(n) = G(G(n-1)) 0 0 1 1 1 2 2 3 3 3 4 4 4 5 5 6 G(G(15)) = G(15 - G(G(14))) = G(15 - 6) = 6 G(G(16)) = G(16 - 6) = 6 G(G(17)) = G(17 - 6) = 7 G(G(18)) = G(18 - 7) = 7 G(G(19)) = G(19 - 7) = 8 G(G(20)) = G(20 - 8) = 8 G(G(21)) = G(21 - 8) = 8

Recognitions:
Homework Help

## Help me find the recursive formula

Try looking at F(F(n)) or F(F(n-1)) (either one, it doesn't matter). It seems to also take the pattern 3, 3, 2, 3, 3, 2, 3, 3, 2, ... in terms of groupings of consecutive arguments that have the same values. If we looked at I(n) and G(G(n-1)) separately, we'd notice a similar pattern, and since I(n) is just the difference between n and G(n), we'd know that G(G(n-1)) gives us our "error" in terms of how far G(n) deviates from n. If H(n) and F(F(n)) also follow the same pattern, then we can guess that F(F(n)) tells us our error (plus or minus a constant).

 Thank you for your interest. Here is a .jpg of the G(n) tree. The F(n) numbers are written beside them in pencil. Notice how G(n) has the Fibonacci sequence running up the right hand side. Thus F(n) has the sequence running up the left hand side.

Recognitions:
Homework Help
 Quote by Skomatth Notice how G(n) has the Fibonacci sequence running up the right hand side.
Great observation. If you can, prove that this will be the case. Now define a function X that takes an number from the G tree and tells you what number it corresponds to on the F tree. If $\phi (n)$ is the nth Fibonacci number, then you can easily see that:

$$X(\phi (n) - a) = \phi (n - 1) + 1 + a$$

for $a \in \{0, 1, \dots , \phi (n) - \phi (n-1) - 1\}$.

We then find that F(n) = X(G(X-1(n))). This is not exactly a closed form solution, but see if you can do something with it.

 Could you explain what this $$\in$$symbol means? I'm not familiar with it. My math education is pre-cal and some self-taught Calculus. For the F(n), you define in your last post, is that the inverse function of X? If so how would you find it?
 Also in the book the author says to find an algebraic definition for the tree, but he doesn't say that it must be formed in the same way as G(n). So for example we could put F(n) above n instead of under it, or call F(n) n and n F(n) instead of the way we started.
 Recognitions: Homework Help Science Advisor That symbol means that a is an element of the set {0, 1, ... whatever}. Note that the definition I gave you for X may not be helpful just like that. If you just look at the nodes, (and not the way they're connected) then the F tree is just a mirror image of the G tree. Basically, each group of numbers between consecutive Fibonacci numbers gets flipped, as you should be able to see. My function X as written just says the above in the form of an equation, but as it is, it may not help you get a closed form solution for F(n). However, you do know that the Fibonacci function is recursive, so you might be able to work with it. So you could write $$\phi (n) - a = X^{-1}(\phi (n - 1) + 1 + a)$$ but again, this is no more helpful than the definition for X. Basically, with the above definition for X, I have given a formula for F that works, but clearly, it's not a very nice one, not as nice as the one for G. But try to play around with it to see if you get somewhere. I'll try too when I'm not at work. Was post # 8 supposed to have a question?
 There was no question in 8. So basically you can pick whatever a you want to make it work?

Recognitions:
Homework Help