- Get link
- X
- Other Apps
Hofstadter mentions the following recursive relation in his great book "Gödel, Escher, Bach": g(0)=0;g(n)=n−g(g(n−1)). I claim that g(n)=⌊ϕ⋅(n+1)⌋, where ϕ=−1+√52, and I'll show this using a technique that makes proving many identities of this type nearly automatic. Let ϕ⋅n=⌊ϕ⋅n⌋+e, where 0<e<1 as ϕ is irrational, nor can e=1−ϕ, and note that ϕ satisfies ϕ2+ϕ−1=0. Some algebra gives \[ \begin{align} n-\left\lfloor \left( \left\lfloor \phi\cdot n \right\rfloor + 1 \right) \cdot \phi \right\rfloor &= n-\left\lfloor \left( n\cdot \phi - e + 1 \right) \cdot \phi \right\rfloor \\ &= n-\left\lfloor n\cdot {\phi}^2 - e\cdot \phi + \phi \right\rfloor \\ &= n-\left\lfloor n\cdot \left(1-\phi\right) - e\cdot \phi + \phi \right\rfloor \\ ...