1. Theorem: for n >= 6, a(n) < (Sum_{i=1..n-1} a(i)) - a(n-3).

Proof:

Define, for positive integers n, the set B(n) = {a(1), .., a(n)}.

Define, for positive integers n, the set E(n) = the set of all positive integers which cannot be written as a sum of distinct elements of B(n).

Define, for positive integers n, S(n) = Sum_{i=1..n} a(i) = Sum_{b an element of B(n)}.

1.1. Lemma: if a(n) < S(n)/2, and p is an element of E(n), and p < a(n), then S(n) - p is an element of E(n).

Proof of 1.1 by contradiction: assume a(n) < S(n)/2, and p is an element of E(n), and p < a(n), and S(n) - p is not an element of E(n).

Then by the definition of E, there exists M a subset of B(n) such that Sum_{m an element of M} = S(n) - p.

Let C = B(n) \ M.

S(n) = Sum_{i=1..n} a(i) = Sum{b an element of B(n)} = Sum_{m an element of M} + Sum_{c an element of C}.

S(n) = (S(n) - p) + Sum_{c an element of C}.

p = Sum_{c an element of C}.

Then C is a subset of B(n) such that Sum_{c an element of C} = p. Therefore p can be written as a sum of distinct elements of B(n), therefore p is not an element of E(n). This contradicts with our assumption.

This proves Lemma 1.1.

Define, for positive integers n, the set F(n) = (E(n)) intersect ({f < a(n)}). I.e., F(n) is the set of all positive integers less than a(n) which cannot be written as a sum of distinct elements of B(n).

By the definition of sequence a, for all positive integers n, |F(n)| = Sum_{i=1,..,n - 1}i = (n - 1)n / 2.

For n >= 3, |F(n)| - |F(n-2)| = (n - 1) + (n - 2) = 2n - 3.

This means, for n >= 3, there are exactly (2n - 3) positive integers between a(n-2) and a(n) which cannot be written as a sum of distinct elements of B(n). Call this Lemma 1.2.

1.2. Lemma: for n >= 3, there are exactly (2n - 3) positive integers between a(n-2) and a(n) which cannot be written as a sum of distinct elements of B(n).

Proof of Theorem 1 by induction:

Observe: S(6) = 90.

Observe: a(6) = 39 < S(6) / 2.

Observe: Sum_{i=1..5} a(i)) - a(3) = 44 > a(6).

a(6) < (Sum_{i=1..5} a(i)) - a(3), so the base case for the induction holds.

Assume for some fixed n >= 6, a(n) < (Sum_{i=1..n-1} a(i)) - a(n-3) and a(n) < S(n) / 2.

By Lemma 1.2, there are exactly (2n - 3) positive integers between a(n - 2) and a(n) which cannot be written as a sum of distinct elements of B(n). Let Q be the set of these 2n - 3 integers.

Define the set R = the set of all S(n) - q for all elements q of Q.

For all q an element of Q, q < a(n) which means q < S(n) / 2. This means S(n) - q > S(n) / 2, which means S(n) - q > a(n). Therefore, all elements of R are greater than a(n).

For all q an element of Q, q > a(n - 2) which means S(n) - q < S(n) - a(n - 2). Therefore, all elements of R are less than S(n) - a(n - 2).

By Lemma 1.1., for all q an element of Q, S(n) - q is an element of E(n), i.e., S(n) - q cannot be written as a sum of distinct elements of the set B(n).

|R| = |Q| = 2n - 3. Since n >= 6, 2n - 3 > n + 1.

Therefore, there are more than n + 1 integers between a(n) and S(n) - a(n - 2) which cannot be written as a sum of distinct elements of B(n).

Therefore, by the definition of the sequence a, a(n + 1) < S(n) - a(n - 2).

Therefore, a(n + 1) < (Sum_{i=1..n} a(i)) - a(n - 2).

a(n + 1) < S(n).
S(n + 1) = S(n) + a(n + 1) > 2a(n + 1). Therefore, a(n + 1) < S(n + 1) / 2.

This proves the inductive case, and completes the proof of Theorem 1.

2. Corollary: a(n) = O(x^n) where x = (1 + sqrt(3 + 2sqrt(5)))/2.

Proof:

Observe that x is a positive real solution to the equation x^4 - 2x^3 + x - 1 = 0.

Define the sequence U(n) = x^(n - 1) for integers n >= 1.

2.1. Lemma: for all positive integers n >= 4, U(n) = (Sum_{i=1,..,n-1} U(i)) - U(n - 3) + 1/(x - 1).

Proof of Lemma 2.1 by induction:

U(4) = x^3.

x^4 - 2x^3 + x - 1 = 0.

x^4 - x^3 - x^2 - x^3 + x^2 + x = 1.

(x - 1)(x^3 - x^2 - x) = 1.

x^3 - x^2 - x = 1/(x - 1).

x^3 = x^2 + x + 1/(x - 1).

U(4) = U(3) + U(2) + 1/(x - 1) = (Sum_{i=1,..,3} U(i)) - U(1) + 1/(x - 1).

This proves the base case of induction for Lemma 2.1.

Assume for some fixed positive integer n >= 4, U(n) = (Sum_{i=1,..,n-1} U(i)) - U(n - 3) + 1/(x - 1).

U(n + 1) = x * U(n) = (Sum_{i=2,..,n} U(i)) - U(n - 2) + x/(x - 1)

= (Sum_{i=1,..,n} U(i)) - U(n - 2) + x/(x - 1) - 1

= (Sum_{i=1,..,n} U(i)) - U(n - 2) + 1/(x - 1).

This proves the inductive case, and completes the proof of Lemma 2.1.

Let z = 1000x.

2.2. Lemma: For all positive integers n, a(n) < z * U(n).

Proof by induction:

Observe that the inequality in 2.2 holds for all n <= 6.

Assume that the inequality in 2.2 holds for all positive integers up to some fixed integer n >= 6.

a(n + 1) < (Sum_{i=1..n} a(i)) - a(n - 2) by Theorem 1.

a(n + 1) < Sum_{i=1..n, i <> n-2} a(i).

a(n + 1) < Sum_{i=1..n, i <> n-2} (z * U(i)).

a(n + 1) < z * (Sum_{i=1..n, i <> n-2} U(i)).

a(n + 1) < z * (Sum_{i=1..n} U(i) - U(n - 2)).

a(n + 1) < z * (Sum_{i=1..n} U(i) - U(n - 2) + 1/(x - 1)).

By Lemma 2.1, a(n + 1) < z * U(n + 1).

This completes the proof of Lemma 2.2.

For all positive integers n, a(n) < z * U(n) = (1000x) * (x^(n - 1)) = 1000 * x^n.

Therefore, a(n) = O(x^n). This completes the proof of Corollary 2.