Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = 2\int_{-1}^x(f_{n-1}(2t+1)-f_{n-1}(2t-1))\mathrm{d}t $$ It's very clear that this converges against some function and that quite rapidly, as seen in this image, showing the first 8 terms: first 8 functions of the given recursion. Degrees 0 to 7

Furthermore, the derivatives of it have some very special properties.
Note how the (renormalized) derivatives consist of repeated and rescaled functions of the previous degree which is obviously a result of the definition of the recursive integral:
Degree 7 function, along with first and second derivative, each normalized to have same magnitude.

Basically by trying around, I found the following probably more usable Fouriertransform of the expression above. I do not have a formal proof but it holds for all terms I tried it with (first 11). $$ \mathcal{F}_x\left[f_n(x)\right](t)=\frac{\sin \left(2^{-n} t\right) \left(\prod _{k=1}^n \frac{2^{k+1} \sin \left(2^{-k} t\right)}{t}\right)}{\sqrt{2 \pi } t}$$
Here an image of how that looks like (first 10 terms in Interval $[-8\pi,8\pi]$):
Fourierspectrum of first 10 terms

With this, my question becomes:
"What, if there is one, is the closed form inverse fourier transform of $\mathcal{F}_x\left[f_n(x)\right](t)=\frac{\sin \left(2^{-n} t\right) \left(\prod _{k=1}^n \frac{2^{k+1} \sin \left(2^{-k} t\right)}{t}\right)}{\sqrt{2 \pi } t}$, especially for the case $n\rightarrow\infty$?"

On an unrelated note: This is my first question here, so I hope I did pose it decently. I searched through mathstack, to my best knowledge using terms of the involved math, without success.

(minor Edit: it seems like the image sharing service I'm using tends to be somewhat unreliable. I'm sorry for that. If some or all of the images don't show up, that's why.)

share|cite|improve this question
The integral has unbalanced parentheses and no limits; the right-hand side isn't a well-defined function of $x$. Also, in mathematics, when defining functions by cases one doesn't usually follow the programming convention of implying a conjunction with earlier conditions in later conditions, but states mutually exclusive conditions. – joriki Nov 19 '12 at 16:46
@joriki: I tried to improve what you said. Is that correct now? I'm not sure what I'm supposed to do with the conditions. Can you clarify, please? – kram1032 Nov 19 '12 at 17:03
The limits are OK now; I would have added an opening parenthesis instead of removing the closing one, to clarify the scope of the integral; about the conditions, I'd write $\begin{cases}1/2&|x|\lt1\;,\\0&|x|\ge1\;.\end{cases}$ – joriki Nov 19 '12 at 17:13
@joriki thank you for your input! Is this how you'd like it? – kram1032 Nov 19 '12 at 17:17
nathang 19:50 Note f_n(0) = 1 for n>0, so (f_n)'(-1/2) = 4 for n>1. So it can't be the box function. – Peter Sheldrick Nov 20 '12 at 21:52
up vote 12 down vote accepted

Here is a formula for $f_n$:

\[ f_n(x) = \sum_{j=0}^{2^n} \left( \frac{c_n(j) - c_n(j-1)}{2}\frac{\left(2^n x + 2^n - 2j\right)^n H\left(2^nx + 2^n - 2j\right)} {n!2^{n(n-1)/2}} \right). \]

Here $H$ is the Heaviside step function, $c_n$ is defined by \[ c_n(j) = \begin{cases} 0 & \text{if $j<0$}\\ (-1)^{s(j)} & \text{if $0\leq j < 2^n$} \\ 0 & \text{if $j\geq 2^n$} \end{cases} \] and $s(j)$ is the sum of the digits of the binary representation of $j$. (For example $s(13) = s(0\text{b}1101) = 3$.)

While the Heaviside function is crucial to deriving the formula, it can be removed from the final result using the floor function (denoted $\lfloor \cdot \rfloor$):

\[ f_n(x) = \sum_{j=0}^{\lfloor2^{n-1}(x+1)\rfloor} \left( \frac{c_n(j) - c_n(j-1)}{2}\frac{\left(2^n x + 2^n - 2j\right)^n} {n!2^{n(n-1)/2}} \right). \]

Here is a plot of $f_{15}$ using this formula:


Deriving the formula

First, separate the definition into two integrals and change variables, $2t+1 \mapsto t$ in the first, and $2t-1\mapsto t$ in the second, giving

\[ f_{n+1}(x) = \int_{-1}^{2x+1} f_n(t)\ dt - \int_{-3}^{2x-1}f_n(t)\ dt \]

Of course, we can change the -3 to -1 and combine these to a single integral:

\[ f_{n+1}(x) = \int_{2x-1}^{2x+1} f_n(t)\ dt \]

Then rewrite $f_0=(1/2)(H(t+1) - H(t-1))$. Note that the integral of $H(t)$ is $tH(t)$, whose integral is $(t^2/2)H(t)$, and so forth. Now we can write $f_n$ as a single iterated integral, for example

\[ f_3(x) = \frac12 \int_{2x-1}^{2x+1} \int_{2y-1}^{2y+1} \int_{2z-1}^{2z+1} (H(t-1) - H(t+1))dt\ dz\ dy \]

Each integration can be done doing several different changes of variables. This gives rise to the powers of 2 in the denominator.


Each $f_n$ is symmetric. The part from -1 to -0.5 is repeated four times. Due to the way that Heaviside functions work, it is computationally easiest to compute values for $f_n(x)$ for $x$ closer to -1.


Here is some Python code to compute $f_n(x)$.

from __future__ import division
from math import factorial

def c(j, n):
    if j < 0 or j >= 2**n:
        return 0
        return (-1)**bin(j).count("1")

def f(x, n):
    numerator = 0
    for j in xrange(int(2**(n-1) * (x+1))):
        numerator += (c(j, n) - c(j-1, n)) * (2**n * x + 2**n - 2*j)**n
    denominator = 2 * 2**(n*(n-1)/2) * factorial(n)
    return numerator/denominator

print f(-0.75, 10)
share|cite|improve this answer

Suppose $f$ is a fixed point of the iterations. Then $$f(x) = 2\int_{-1}^x\big(f(2t+1)-f(2t-1)\big)\,\mathrm{d}t,$$ which, upon differentiating both sides by $x$, implies that $$f'(x) = 2\big(f(2x+1)-f(2x-1)\big).$$ I'll assume that $f$ vanishes outside $[-1,1]$, which you can presumably prove from the initial conditions. Then we get $$f'(x) = \begin{cases} 2f(2x+1) & \text{if }x\le0, \\ -2f(2x-1) & \text{if }x>0. \end{cases}$$ This is pretty close to the definition of the Fabius function. In fact, your function would be $\frac{\text{Fb}'(\frac{x}{2}+1)}{2}$

The Fabius function is smooth but nowhere analytic, so there isn't going to be a nice closed form for your function.

share|cite|improve this answer
Wikipedia has an alternative definition that's closer to your repeated integrations, but it gives what the other page calls $\operatorname{Fb}'(x)$ instead of $\operatorname{Fb}(x)$. – Rahul Nov 24 '12 at 16:32
Ah, nice. So my type of function now has a name. Good to know. - It's always hard to research stuff you have no idea how it's called. I already suspected this kind of thing to be tried. - It's too simple an idea to be new. – kram1032 Nov 24 '12 at 17:16
Heh, you know, I too reinvented the Fabius function before I knew what it was, though through a slightly different route. You may recognize your Fourier transform in my question. – Rahul Nov 24 '12 at 17:31
Nice, so I guess our two questions are related. – kram1032 Nov 24 '12 at 17:35
Now that I know the name, a quick google search even gives another related question on mathoverflow: – kram1032 Nov 25 '12 at 0:43

This equation \begin{equation}f'(x)=2f(2x+1)-2f(2x-1), \quad f(0) = 1, \tag{$*$} \end{equation} has a finite solution which is also known as the $\mathrm{up}(x)$ or $\mathrm{hut}(x)$ function. It has compact support $\mathrm{supp}\,\mathrm{{up}}(x)=[-1,1]$ and its Fourier transform is $\hat{f}(t)=\prod\limits_{k=1}^{\infty}\mathrm{sinc}{(t\cdot 2^{-k})}.$ So, $\mathrm{up}(x)$ is defined by inverse Fourier transform as follows $$ \mathrm{up}(x)=\frac{1}{2\pi}\int\limits_{\mathbb{R}}e^{-itx}\hat{f}(t)\,dt= \frac{1}{2\pi}\int\limits_{\mathbb{R}}e^{-itx}\prod\limits_{k=1}^{\infty}\mathrm{sinc}{(t\cdot 2^{-k})}\,dt. $$

Equation $(*)$ and its finite solution $\mathrm{up}(x)$ was independently introduced in 1971 by V.L. Rvachev, V.A. Rvachev and W. Hilberg. It's interesting to note that a simpler version of $(*)$ was introduced by J. Fabius only 5 years earlier: \begin{equation}f'(x)=2f(2x), \quad f(0) = 0. \tag{$**$} \end{equation} By the way, the signs of the first 2 derivatives of $\mathrm{up}(x)$ are the elements of Thue-Morse sequence $\{+1,-1,-1,+1\}$ as well.

P.S. I've uploaded some plots here of generalizations of $\mathrm{up}(x)$ which is known as the $\mathrm{h}_a(x)$ function.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.