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.