# Number of superincreasing sequences of natural numbers

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

-

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