Number of superincreasing sequences of natural numbers

Solution 1:

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.

Solution 2:

In fact, the sequence is described in details of A125792. The number I was looking for is the same as the number of partitions of $2^n$ into powers of $2$, excluding the trivial partition $2^n=2^n$ (note there by Valentin Bakoev).

Perhaps the easiest practical recurrent formula is the following: $$ T(n,k) = T(n,k-1) + T(n-1,2k) $$ $$ T(n,0) = T(0,k) = 1 $$

Then the answer to the original problem is $T(n,2)$.

One can find even more discussion and references in the description of A002577 which is $T(n,2) + 1$ (in our notation).