MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


  • 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):

Graph of f

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

Graph of f

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

Plot of Hofstadter's Q sequence

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.