Superincreasing sequences

This article page is a stub, please help by expanding it.

A sequence of positive real numbers $\scriptstyle \{a_{n}\}$ is called superincreasing if every element of the sequence is greater than the sum of all previous elements in the sequence, i.e.

$a_{n+1}>\sum _{i=0}^{n}a_{i},\quad \forall n\geq 0.$

Examples

For example, {1, 3, 6, 13, 27, 52} is a superincreasing sequence, but {1, 3, 4, 9, 15, 25} is not.

Python source code example

The following Python source code tests a sequence of numbers to determine if it is superincreasing

sequence = [1,3,6,13,27,52]
sum = 0
test = True
for n in sequence:
    print "Sum: ", sum, "Element: ", n
    if n <= sum: 
        test = False
        break
    sum += n

print "Superincreasing sequence? ", test

and produces the following output

 Sum:  0 Element:  1
 Sum:  1 Element:  3
 Sum:  4 Element:  6
 Sum:  10 Element:  13
 Sum:  23 Element:  27
 Sum:  50 Element:  52
 Superincreasing sequence?  True

Minimally superincreasing integer sequences

A sequence of positive integers $\scriptstyle \{a_{n}\}$ might be said to be minimally superincreasing if every element of the sequence is equal to the sum of all previous elements in the sequence, plus one, i.e.,

$a_{n+1}=\left(\sum _{i=0}^{n}a_{i}\right)+1,\quad \forall n\geq 0.$

The minimally superincreasing sequence of positive integers starting at $\scriptstyle h,\,h\,\geq \,1,$ is thus

$\{h,h+1,2h+2,4h+4,8h+8,16h+16,32h+32,64h+64,\ldots \}=\{h,h+1,2(h+1),4(h+1),8(h+1),16(h+1),32(h+1),64(h+1),\ldots \}$

given by the formula

$a_{n}={\begin{cases}h&{\mbox{if }}n=0,\\(h+1)2^{n-1}&{\mbox{if }}n\geq 1.\end{cases}}$

The sequence of powers of 2 is the "minimal" (i.e. with lowest terms) minimally superincreasing integer sequence

The "minimal" (i.e. with lowest terms, corresponding to $\scriptstyle h\,=\,1$) minimally superincreasing (positive) integer sequence is thus

{1, (1) + 1 = 2, (1+2) + 1 = 4, (1+2+4) + 1 = 8, (1+2+4+8) + 1 = 16, (1+2+4+8+16) + 1 = 32, (1+2+4+8+16+32) + 1 = 64, (1+2+4+8+16+32+64) + 1 = 128, ...}

which is the sequence of nonnegative powers of two

$a_{n}=2^{n},\quad n\,\geq \,0.$

This results from the well-known formula

$2^{n+1}=\left(\sum _{i=0}^{n}2^{i}\right)+1,\quad n\,\geq \,0.$

This implies that superincreasing sequences of positive integers grow at least as fast as the sequence of powers of 2, thus excluding sequences with polynomial growth, sequences with subexponential growth or sequences with exponential growth but with base less than two (e.g. the Fibonacci sequence, which is asymptotic to $\scriptstyle {\frac {{\varphi }^{n}}{\sqrt {5}}}=$ (1.6180339887499...)  / 2.2360679774998...)

Suppose that a positive real number $\scriptstyle x\,=\,\sum _{j=0}^{n}c_{j}\,a_{j}$. If $\scriptstyle \{a_{j}\}$ is a superincreasing sequence of positive real numbers and every $\scriptstyle c_{j}\,\in \,\{0,\,1\}$, then we can always determine the unique $\scriptstyle c_{j}$'s simply by knowing $\scriptstyle x$, e.g. via a greedy algorithm. If $\scriptstyle \{a_{j}\}\,=\,\{2^{j}\}$ then every positive real number is represented (in a unique way.) This is analogous to the fact that, for any natural number, we can always determine which bits are on and off in the binary bitstring representing the number.

k-superincreasing sequences

This is a proposed definition, which may be removed if not considered of interest. — Daniel Forgues 06:03, 21 October 2011 (UTC)

A sequence of positive real numbers $\scriptstyle \{a_{n}\}$ could be called k-superincreasing if every element of the sequence is greater than $\scriptstyle k$ times the sum of all previous elements in the sequence, i.e.,

$a_{n+1}>k\left(\sum _{i=0}^{n}a_{i}\right),\quad \forall n\geq 0.$

Superincreasing correspond to the case $\scriptstyle k\,=\,1$.

Minimally k-superincreasing integer sequences

A sequence of positive integers $\scriptstyle \{a_{n}\}$ could thus be said to be minimally $\scriptstyle k$-superincreasing if every element of the sequence is equal to $\scriptstyle k$ times the sum of all previous elements in the sequence, plus one, i.e.,

$a_{n+1}=k\left(\sum _{i=0}^{n}a_{i}\right)+1,\quad \forall n\geq 0.$

The minimally $\scriptstyle k$-superincreasing sequence of positive integers starting at $\scriptstyle h,\,h\,\geq \,1,$ is thus

$\{h,\,k[h]+1=kh+1,\,k[h+(kh+1)]+1=(k+1)(kh+1),\,k[h+(kh+1)+(k+1)(kh+1)]+1=(k+1)^{2}(kh+1),$

$k[h+(kh+1)+(k+1)(kh+1)+(k+1)^{2}(kh+1)]+1=(k+1)^{3}(kh+1),\,\ldots \}$

given by the formula

$a_{n}={\begin{cases}h&{\mbox{if }}n=0,\\(kh+1)(k+1)^{n-1}&{\mbox{if }}n\geq 1.\end{cases}}$

The sequence of powers of (k+1) is the "minimal" (i.e. with lowest terms) minimally k-superincreasing integer sequence

The "minimal" (i.e. with lowest terms, corresponding to $\scriptstyle h\,=\,1$) minimally $\scriptstyle k$-superincreasing (positive) integer sequence is thus

$\{1,k[1]+1=k+1,k[1+(k+1)]+1=(k+1)^{2},k[1+(k+1)+(k+1)^{2}]+1=(k+1)^{3},k[1+(k+1)+(k+1)^{2}+(k+1)^{3}]+1=(k+1)^{4},\ldots \}$

which is the sequence of nonnegative powers of $\scriptstyle k+1$

$a_{n}=(k+1)^{n},\quad n\,\geq \,0,\,k\,\geq \,1.$

This results from the well-known formula

$(k+1)^{n+1}=k\left(\sum _{i=0}^{n}(k+1)^{i}\right)+1,\quad n\,\geq \,0,\,k\,\geq \,1.$

For example, $\scriptstyle k\,=\,9$ gives

{1, 9 * (1) + 1 = 10, 9 * (1+10) + 1 = 100, 9 * (1+10+100) + 1 = 1000, 9 * (1+10+100+1000) + 1 = 10000, 9 * (1+10+100+1000+10000) + 1 = 100000, 9 * (1+10+100+1000+10000+100000) + 1 = 1000000, ...}

This implies that $\scriptstyle k$-superincreasing sequences of positive integers grow at least as fast as the sequence of powers of $\scriptstyle (k+1)$, thus excluding sequences with polynomial growth, sequences with subexponential growth or sequences with exponential growth but with base less than $\scriptstyle (k+1),\,k\,\geq \,1.$

Suppose that a positive real number $\scriptstyle x\,=\,\sum _{j=0}^{n}c_{j}\,a_{j}$. If $\scriptstyle \{a_{j}\}$ is a $\scriptstyle k$-superincreasing sequence of positive real numbers and every $\scriptstyle c_{j}\,\in \,\{0,\,k\}$, then we can always determine the unique $\scriptstyle c_{j}$'s simply by knowing $\scriptstyle x$, e.g. via a greedy algorithm. If $\scriptstyle \{a_{j}\}\,=\,\{(k+1)^{j}\}$ then every positive real number is represented (in a unique way.) This is analogous to the fact that, for any natural number, we can always determine which are the digits in the base (k+1) numeral system represention of the number.

See also

• Growth of sequences
• Merkle-Hellman knapsack cryptosystem