# Re: Closed form of the Hofstadter G-Sequence

*From*: torteloni@xxxxxxxxxxxxxx*Date*: Sun, 25 Jan 2009 09:50:02 -0800 (PST)

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

.

**References**:**Closed form of the Hofstadter G-Sequence***From:*torteloni

**Re: Closed form of the Hofstadter G-Sequence***From:*hagman

- Prev by Date:
**Re: Optimising files on a DVD -any algorithm better than brute-force approach?** - Next by Date:
**Re: ---- ---- --- A question in trigonometry** - Previous by thread:
**Re: Closed form of the Hofstadter G-Sequence** - Next by thread:
**Defn "Strongly Continuous Vector Valaued Function"** - Index(es):