## Saturday, October 11, 2014

### A Strange Recursive Relation, Automatic

Hofstadter mentions the following recursive relation in his great book "Gödel, Escher, Bach": \begin{align} g(0) &= 0;\\ g(n) &= n-g(g(n-1)). \end{align} I claim that $$g(n) = \left\lfloor \phi\cdot (n+1) \right\rfloor$$, where $$\phi = \frac{-1+\sqrt{5}}{2}$$, and I'll show this using a technique that makes proving many identities of this type nearly automatic.

Let $$\phi\cdot n = \left\lfloor \phi\cdot n \right\rfloor + e$$, where $$0 < e < 1$$ as $$\phi$$ is irrational, nor can $$e = 1-\phi$$, and note that $$\phi$$ satisfies $${\phi}^2 + \phi - 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 \\ &= n-n-\left\lfloor -n\cdot \phi - e\cdot \phi + \phi \right\rfloor \\ &= -\left\lfloor -n\cdot \phi - e\cdot \phi + \phi \right\rfloor \\ &= -\left\lfloor -n \cdot \phi + e - e - e\cdot \phi + \phi \right\rfloor \\ &= \left\lfloor \phi\cdot n \right\rfloor -\left\lfloor - e - e\cdot \phi + \phi \right\rfloor. \end{align}
Now if \begin{align} 0 < e < 1-\phi &\implies 0 < - e - e\cdot \phi + \phi < \phi;\\ 1-\phi < e < 1 &\implies -1 < - e - e\cdot \phi + \phi < 0. \end{align}
This implies $n-\left\lfloor \left( \left\lfloor \phi\cdot n \right\rfloor + 1 \right) \cdot \phi \right\rfloor = \left\lfloor \phi\cdot (n+1) \right\rfloor .$ Since $$\left\lfloor \phi\cdot (0+1) \right\rfloor = 0$$, we're done.

The point of the algebra was to move all terms involving $$n$$ out, and then checking to see how the remaining term varied with $$e$$. A simple idea, but very useful.

## Sunday, October 5, 2014

### Closed Under Means

Here's a nice little problem from the 13th All Soviet Union Mathematics Olympiad.
Given a set of real numbers $$S$$ containing 0 and 1 that's closed under finite means, show that it contains all rational numbers in the interval $$\left[0,1\right]$$.
This isn't a difficult problem, but there's a particularly nice solution.

First observe that if $$x\in S$$ then both $$\frac{x}{4}$$ and $$\frac{3x}{4}$$ are in $$S$$; average $$\{0,x\}$$ to get $$\frac{x}{2}$$, average $$\{0, \frac{x}{2}\}$$ to get $$\frac{x}{4}$$, average $$\{\frac{x}{2}, x\}$$ to get $$\frac{3x}{4}$$.

We could show any rational number $$\frac{m}{n}$$ with $$1\leq m < n$$ is in $$S$$ if we had $$n$$ distinct elements from $$S$$ that summed to $$m$$. Let's exhibit one.

Start with an array with $$m$$ 1s on the left, $$n-m$$ 0s on the right. Repeatedly replace adjacent $$x,y$$ values with $$\frac{3(x+y)}{4}, \frac{(x+y)}{4}$$, where either $$x=1,y\neq1$$ or $$x\neq 0, y=0$$, until there is one 0 and one 1 left. We can do this in exactly $$n-2$$ steps, each resulting number is guaranteed to be in $$S$$ by the above note, and each number is guaranteed to be distinct by construction!

Examples:

$$\frac{1}{3}: \left[1,0,0\right] \to \left[\frac{3}{4},\frac{1}{4},0\right]$$

$$\frac{2}{5}: \left[1,1,0,0,0\right] \to \left[1,\frac{3}{4},\frac{1}{4},0,0\right] \to \left[1,\frac{3}{4},\frac{3}{16},\frac{1}{16},0\right]$$