Re: Closed form of the Hofstadter G-Sequence

On 22 Jan., 08:01, hagman <goo...@xxxxxxxxxxxxx> wrote:

If you do not want the exact details but rather just want to know
where
the PHI comes from, have a look at the recursion
G(n) = n -G(G(n-1))
IF G(n) is approximately c*n for some constant c, then this implies
c*n ~ n - c*c*(n-1)
and dividing by n suggests c = 1 - c^2.

For the exact proof by induction, I think the assumption that
[(n+1)/PHI] is not the same as n-[([n/PHI]+1)/PHI] leads to
an impossibly good rational approximation of PHI.

Thanks for this hint. This already helps me a lot (and is a really
interesting idea I think). Do you have any more idea for me how that
closed form can be proved? Or do you have any idea for helpful
literature about that? The only literature references I found are in
"Gödel, Escher, Bach" (but there is not too much information in it)
and some English science magazines - and most of them I cannot get as
a German pupil....
.