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

The function is given as

$$f(x)\geq \sum_{i=1}^{[x/2]}f(i)+1$$

The boundary condition is $f(0)=0$.

What I can get is this function grows faster than any polynomial function, and grows slower than any exponential function.

Apparently this function is monotonic, estimate in the integral form gives

$$f(x)\geq \int_{i=0}^{x/2-1}f(t)dt+1$$ must be satisfied.

I also tried put $\geq$ as equality and solve the ODE obtained, which looks like $f(x)=2f'(2x)$. But I could not go any further.

So is there some way to estimate the growth of this function? More specifically, I would like know how to find some asymptotic lower bound which is better than polynomials. Thanks

share|cite|improve this question
Doesn't $f(x) = e^{x/2}$ satisfy the equation? – Ron Gordon Jan 18 '13 at 3:41
It satisfies the inequality, not the version that is an equation. – Robert Israel Jan 18 '13 at 3:43
up vote 1 down vote accepted

With $\ge$, this does not define the function uniquely. It might grow exponentially or faster, e.g. $2^x$ satisfies the inequality.

For the version with $=$, see

EDIT: This is the version of with terms repeated. Precise asymptotics are given in N. G. de Bruijn, "On Mahler's partition problem", Indagationes Mathematicae, vol. X (1948), 210-220.

share|cite|improve this answer
Sorry I was not clear enough before. Actually I was looking for some good lower bound for this function. – Jiajun Wu Jan 18 '13 at 4:55

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.