Help me find the recursive formula

[Skomatth]

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.

 

[AKG]

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

 

[AKG]

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

 

[AKG]

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

 

[Skomatth]

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.

 

[AKG]

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 n^th 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.

 

[Skomatth]

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?

 

[Skomatth]

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.

 

[AKG]

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?

 

[Skomatth]

There was no question in 8. So basically you can pick whatever a you want to make it work?

 

[AKG]

There was no question in 8. So basically you can pick whatever a you want to make it work?

I'm not sure what you mean. If I define a function f by f(x) = x², what you're asking is like asking, "so you can pick any "x" you want to make it work?" Basically, if you have some node n on the G-tree, and you know what number it occurs at, then X(n) tells you the number it corresponds to on the F-tree. Maybe you have to think about how I got X to understand what's going on. Basically, you can see that the tree is divided up into levels, and level n contains every number greater than the n-1^th Fibonacci number up to and including the n^th. Going from G to F just flips these levels horizontally. Now let's say you had numbers 0 through m, and you were at some number a in this list. Now, if you flipped these numbers around you'd be at m - a, right? And so obviously if you start at m - a, you'll end up at a. Think about this and see if you can see why the definition of X makes sense.

Also, it occurred to me that since X really is just like flipping, X is self-inverse, so we could simply write F(n) = X(G(X(n))). Not sure if that's any more helpful.