# Finding the lowest sum of the sequence possible given some conditions

Say we have an infinite sequence of natural numbers $A$ such that no $k$ subsequences can be found adjacent such that the average of the elements in any subsequence is equal for all $k$ subsequences. Sorry about my poor description, an example would be that $\{2, 3, 4, 1\}$ wouldn't work for $k=2$ because $\{2, 3\}$ and $\{4, 1\}$ are adjacent and both their averages are $\frac{5}{2}$. $\{2, 3, 10, 4, 1\}$ would work however because $\{2, 3\}$ and $\{4, 1\}$ are no longer adjacent. Anyway, my question is: which sequence that follows this has the lowest sum for $k$? If that's too general, then which for $k=2$? Honestly, any information on the behavior of this sequence would be great. To me, it looks like for $k=2$ is $\{1, 2, 1, 3, 1, 2, 1, 4 ...\}$ but I have no idea how to prove that it is. Thanks.

-
"which sequence that follows this has the lowest sum?" Any infinite sequence of natural numbers has infinite sum, so it's not clear what you mean by "lowest sum". –  Gerry Myerson Jan 24 '13 at 2:57
Also, if you carry out your $k=2$ sequence one more term, I assume your intention is for the next term to be $1$, but $3,1,2$ and $1,4,1$ have the same sum (whence, same average). –  Gerry Myerson Jan 24 '13 at 3:01
Huh, thanks for pointing that out. Didn't see that initially. And also, is it not true that an infinite sequence of natural numbers has a countably infinite sum, such that $\{1, 1, 1...\}$ is less than $\{2, 2, 2...\}$? –  user1825464 Jan 24 '13 at 3:06
If anything, what I really need to know is if I can show how the sequence can be written in big O notation, maybe it follows $O(x^{1 +n})$? –  user1825464 Jan 24 '13 at 3:29
I don't know of any consistent system in which it can be stated that $1+1+\dots\lt2+2+\dots$. I don't know what you mean by $O(x^{1+n})$ in this context. Do you mean something like, the $n$th term can be taken to be $O(n^k)$? –  Gerry Myerson Jan 24 '13 at 5:30

Let's try to sharpen the question:

Your example shows that you are considering non-overlapping subsequences of $A$, i.e., you partition $A$ into fragments of fixed length. So let's try some definitions:

1. For any sequence $s$, let $W_k(s)$ be the sequence whose $n$th term (counting from 0) is given by $s_{kn} + s_{kn+1} + s_{kn+2} + ... + s_{kn+k-1}$. Note that since the average of $k$ numbers is just their sum divided by $k$, we can consider sums instead of averages. ($W$ is for window: A fixed-length fragment).

2. For any sequence $s$, define $\Sigma s$ to be the sequence whose $n$th term is the sum of the first $n$ terms of $s$.

3. For two sequences $s$ and $t$, we say that $s < t$ if there is some $m \in N$ such that $s_n < t_n$ for all $n > m$ (I.e., $s<t$ "in the limit").

So, for any $k$ you want to find the sequence $A$ that satisfies the following:

1. $W_k(A)$ has no adjacent terms that are equal.

2. If $B$ is another sequence for which $W_k(B)$ has no repeated terms, $\Sigma A < \Sigma B$ (in the sense of definition 2).

If all this is correct, my candidate for minimum at $k=2$ would be the following periodic sequence (I have bracketed the period):

$$A = [ 1, 1, 1, 2, ] 1, 1, 1, 2, ...$$

This matches the condition, since $W_2(A) = 2, 3, 2, 3, ...$.

I believe it's pretty easy to see how to construct similar sequences for $k > 2$. A more interesting problem would be if you misunderstood the conditions, and the adjacent subsequences are overlapping rather than disjoint. (E.g., terms $s_0s_1, s_1s_2, s_2s_3, ...$).

-