Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Let us define a superincreasing sequence of natural numbers $b_1, b_2, \ldots,b_n$:

$$ b_{i+1} > \sum_{j=1}^i b_j $$

or, as we talk about natural numbers:

$$ b_{i+1} \geq 1+ \sum_{j=1}^i b_j. $$

What is the number of such sequences with the following property:

$$ \sum_{j=1}^n b_j \leq 2^{n+1}-1. $$

A simple lower-bound estimate is $n+1$ - this is the number of superincreasing sequences which consist of powers of 2, i.e. $n$-combinations of set $\{1,2,4,\ldots,2^n\}$.

In case this is complicated to find simple exact formula, estimates will be interesting too.

UPD 1. Program generation showed the following results for the first values of $n$: 3, 9, 35, 201, 1827, 27337, 692003, 30251721... This is OEIS A125792. Also I post links to sequences I generated for $n=2$, $n=3$ and $n=4$.

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

I find $\begin {array} {c c} n& \text{sequences}\\1&3\\2&9\\3&35\\4&201 \end {array}$

which is OEIS A125972. The counting is suggestive. For $n=3$ there are $9$ beginning $1,2$; $7$ beginning $1,3$; down to $1$ beginning wit $1,6$ for a total of $25$ beginning with $1$. Similarly there are $9$ beginning with $2$ and $1$ beginning with $3$. For $n=4$ there are $9^2$ beginning $1,2$; $7^2$ beginning $1,3$; down to $1^2$ beginning $1,6$ for $165$ beginning with $1$, and again $95^2$ beginning $2,3$ and so on. It clearly needs some induction.

share|cite|improve this answer
I generated all the sequences for small $n$'s and found a bit different numbers: 3, 9, 35, 201, 1827, 27337, 692003, 30251721... And this is A125792. – Yauhen Yakimenka Nov 3 '12 at 2:27
Seems to be a bit of disagreement at $n=4$. Perhaps you could both check your calculations. – Gerry Myerson Nov 3 '12 at 4:55
@GerryMyerson: Found the error and fixed – Ross Millikan Nov 3 '12 at 6:09

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.