# The functional equation of Hofstadter's Q sequence

Hofstadter's Q sequence is defined by $Q(1) = Q(2) = 1$ and $Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ for $n \geq 3$. So far hardly anything on this sequence has been proved -- not even that $Q(n)$ is well-defined for all positive integers $n$.

Put $a := \frac{1}{4}(9 - \sqrt{89})$, and let $$f: \mathbb{R} \rightarrow \mathbb{R}, \ \ x \mapsto \begin{cases} ax^3 + \left(\frac{1}{2} - 6a\right)x^2 + \left(11a-\frac{3}{2}\right)x + 2 - 6a & \text{if} \ x \leq 3, \\\ f(x-f(x-1)) + f(x-f(x-2)) & \text{if} \ x > 3. \\\ \end{cases}$$ Then the function $f$ is well-defined (note that $\forall x \in \mathbb{R} \ f(x) > 0$), continuous and differentiable at all $x \in \mathbb{R}$, and we have $f(n) = Q(n)$ for any positive integer $n$ for which $Q(n)$ is well-defined. Also, by construction for $x \geq 3$ the function $f$ satisfies the functional equation $f(x) = f(x-f(x-1)) + f(x-f(x-2))$ (but obviously it does not do so for $x < 3$).

Questions:

• What can be said about the function $f$ besides these basic facts?

• Does the functional equation $f(x) = f(x-f(x-1)) + f(x-f(x-2))$ have continuous and differentiable (or at least continuous) solutions $f: \mathbb{R} \rightarrow \mathbb{R}$ other than the zero function?

• Or to be a bit more bold: does it have solutions $f: \mathbb{C} \rightarrow \mathbb{C}$ other than the zero function which are meromorphic on the complex plane?

Remarks: The graph of the function $f$ for $-1 \leq x \leq 15$ looks as follows (the graph of the polynomial used to define $f$ for $x \leq 3$ is shown in red):

The graph for $-1 \leq x \leq 23$ looks as follows:

A plot of the first 576 terms of Hofstadter's Q sequence looks like this:

-
Presumably you mean $f(x) = f(x−f(x−1))+f(x−f(x−2))$? The formula "$f(x−f(x−1))+f(x−f(x−2))$" itself is not a functional equation. – Noam D. Elkies Jun 20 '13 at 16:39
Nice pictures. Suppose instead of your polynomial you use a straightline approximation: choice 1 is f=1 for (0,2] and (x-1) for [2,3], while choice 2 is f=x on (0,1) and otherwise looks like choice 1. Can you comment on the results for either of these choices? Gerhard "Maybe Make Pretty Graphs Too?" Paseman, 2013.06.20 – Gerhard Paseman Jun 20 '13 at 16:46
@Noam: Of course. -- Thanks for spotting the typo. – Stefan Kohl Jun 20 '13 at 19:27
@Gerhard: A straightline approximation won't do -- you won't get a function which is continuous and differentiable at $x=3$. Making the function differentiable at $x=3$ requires the 'complicated' polynomial. – Stefan Kohl Jun 20 '13 at 19:33
Yes, but until one gets to the word "meromorphic" in your post, there is no hint that differentiability is a concern of yours. I thought your issue would be whether it results in a total function on the reals greater than or equal to 1. In any case, it would be of interest to see if the function needs to be defined on (0,1) in the straightline version for the functional part of the definition to work. Gerhard "With Sides Reversed Is Not" Paseman, 2013.06.20 – Gerhard Paseman Jun 21 '13 at 1:47