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

Is there a solution/approximation for the non-linear difference equation $c_n = c_{n-1}+c_{\lceil \alpha n \rceil}$, where $0 < \alpha < 1$?

share|cite|improve this question
up vote 6 down vote accepted

As Aaron Meyerowitz mentions when $\alpha=\frac{1}{b}$ the sequence is related to the number of partitions of $bn$ into powers of $b$. The asymptotic value of this sequence was determined by de Bruijn (On Mahler's partition problem). I believe his methods can be used to get asymptotic values for general $\alpha$, though I haven't checked this carefully. By looking at the generating function you can reduce it to studying the asymptotics of the coefficients of a power series $F(x)$ (which should be approximately the generating function of your sequence) which satisfies $$F(x)=\frac{1-x^{\lceil 1/\alpha\rceil}}{(1-x)^2}F(x^{\lceil 1/\alpha\rceil})$$ this is a Mahler type functional equation, and there are standard methods in the literature to obtain asymptotics.

share|cite|improve this answer

Here is the case $\alpha=1/2.$ with rounding down. It shows conjectures but few results. But you asked about rounding up. That is here and it seems that more is known in this $\alpha=1/2$ case including a good estimte of the growth rate. The $nth$ term is the number of partitions of $2n$ into powers of 2.

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.