# Superincreasing Sequences

A sequence of positive integers \(a_1, a_2, a_3, ... , a_n\) is termed **superincreasing** when each element is greater than the sum of all previous elements in the sequence. $$a_2 > a_1 \\ a_3 > a_1 + a_2 \\ a_4 > a_1 + a_2 + a_3 \\ \vdots \\ a_n > a_1 + a_2 + ... + a_{n-1}$$

Consider the sequence \(2, 3, 6, 13, 27, \ldots\), which exemplifies a superincreasing sequence because each number surpasses the sum of its predecessors:

$$3 > 2$$

$$2, \color{red}3, 6, 13, 27, \ldots$$

The third term (6) exceeds the sum of the first two terms (5):

$$6 > 2 + 3$$

$$\underbrace{2,3}_{5}, \color{red}6, 13, 27, \ldots$$

The fourth term (13) surpasses the combined total of the first three terms (11):

$$13 > 2 + 3 + 6$$

$$\underbrace{2,3,6}_{11}, \color{red}{13}, 27, \ldots$$

The fifth term (27) exceeds the aggregate of the first four terms (24):

$$27 > 2 + 3 + 6 + 13$$

$$\underbrace{2,3,6,13}_{24}, \color{red}{27}, \ldots$$

### Applications of Superincreasing Sequences

Superincreasing sequences are utilized in various fields, particularly in computational complexity theory and cryptography.

In computational complexity, they are employed to solve certain instances of the **knapsack problem** efficiently.

In cryptography, these sequences form the basis of the Merkle-Hellman knapsack cryptosystem for encoding messages.

**Solving the Knapsack Problem Using a Superincreasing Sequence**

Consider a set of numbers \(N = \{27, 2, 6, 13, 3\}\) with a knapsack capacity limit of 30. The objective is to fill the knapsack completely without exceeding this limit, using as many items from the set as possible, where each item's "volume" corresponds to the numbers provided: 27, 2, 6, 13, and 3. The challenge is to find a combination of these items that perfectly utilizes the knapsack's total volume of 30.

First, the elements of the set are arranged in ascending order to form a sequence:

$$a = \{2, 3, 6, 13, 27\}$$

This sequence is superincreasing, indicating that each element is greater than the sum of all previous elements, allowing the problem to be addressed using a polynomial algorithm. A linear combination of weights \(x_i\), where each can either be 0 or 1, is defined to achieve the target sum:

$$x_1 \cdot a_1 + x_2 \cdot a_2 + x_3 \cdot a_3 + x_4 \cdot a_4 + x_5 \cdot a_5 = m$$

Where \(a_1 = 2\), \(a_2 = 3\), \(a_3 = 6\), \(a_4 = 13\), \(a_5 = 27\), and the total to achieve is \(m = 30\).

$$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + x_5 \cdot 27 = 30 $$

The algorithm starts with the largest element and progressively considers each preceding item until the knapsack is either full or all items have been considered:

**Assigning the last weight:**Compare the volume of the last item with the available space in the knapsack. If the space is sufficient, assign \(x_n=1\); otherwise, \(x_n=0\). $$x_n = \begin{cases} 1 \ \ \text{if} \ \ m \ge a_n \\ 0 \ \ \text{if} \ \ m < a_n \end{cases}$$**Finding preceding weights:**Using the same logic, compare the residual space with the volume of each subsequent item to decide whether it can be included. $$x_i = \begin{cases} 1 \ \ \text{if} \ \ m - \sum_{k=i+1}^n x_k \cdot a_k \ge a_i \\ 0 \ \ \text{if} \ \ m - \sum_{k=i+1}^n x_k \cdot a_k < a_i \end{cases}$$

Steps to solve:

- I start with the largest item \( a_5 = 27 \) and assign \( x_5 = 1 \) if \(a_5 \leq m\); otherwise, \(x_5 = 0\). In this case, \(27 < 30\), so \(x_5 = 1\). This means the item can fit into the knapsack. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$
- I update the remaining space value \( m = m - 27 = 3 \) considering the volume I've already inserted.
- Proceed to the next item \(a_4 = 13\). Since \(13 > 3\), set \(x_4 = 0\) because the knapsack cannot also contain this item. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + \color{red}{0} \cdot 13 + 1 \cdot 27 = 30 $$
- Next, consider \(a_3 = 6\), which cannot fit (\(6 > 3\)), so \(x_3 = 0\) because there is not enough space to insert it into the knapsack. $$ x_1 \cdot 2 + x_2 \cdot 3 + \color{red}{0} \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$
- Then \(a_2 = 3\) matches the remaining space ( $ m = 3 $ ). Thus, I assign the weight \( x_2 = 1 \) because I can fit it into the knapsack. $$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$
- I update the remaining space in the knapsack \( m = 30 - 27 \cdot 1 - 13 \cdot 0 - 6 \cdot 0 - 3 \cdot 1 = 0 \)
- With no space left (\(m = 0\)), the algorithm concludes, leaving \(x_1 = 0\). $$ \color{red}{0} \cdot 2 +1 \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$

The optimal solution combines the volumes \(3\) and \(27\) to exactly fill the knapsack with \(30\):

$$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$

$$3 + 27 = 30$$

This approach is specific to superincreasing sequences and leverages their unique property to find a solution efficiently. It is not applicable if the sequence is not superincreasing.

And so forth.