Alternative formulation: Determine all infinite strings of letters with the following properties: (a) Each letter is either $T$ or $S$, (b) If position $i$ and $j$ both have the letter $T$, then position $i+j$ has the letter $S$, (c) There are infinitely many integers $k$ such that position $2k-1$ has the $k$th $T$.

If $a_k=2k-1$ for some $k>1$, let $A_k=\{a_1,a_2,\ldots,a_k\}$. By (b) and symmetry, we have \[2k-1\ge \frac{|A_k-A_k|-1}{2}+|A_k|\ge \frac{2|A_k|-2}{2}+|A_k| = 2k-1.\]But in order for $|A_k-A_k|=2|A_k|-1$, we must have $A_k$ an arithmetic progression, whence $a_n=2n-1$ for all $n$ by taking $k$ arbitrarily large.

Let $a_1=c$. Lemma: $a_{k+c}\ge a_k+2c$. Proof: Assume $a_{k+c}< a_k+2c$. Consider the sets ${a_k, a_k+c}$, ${a_k+1, a_k+1+c}$, $\cdots$, ${a_k+c-1, a_k+2c-1}$. The sequence is motonic, so each of $a_k$, $a_{k+1},\cdots, a_{k+c}$ must lie in one of the sets. But then by the pigeonhole principle, two numbers in this portion of the sequence must go in the same set, a contradiction to condition b). $\blacksquare$ Now note that \[ a_{mc+1}\ge a_{(m-1)c+1}+2c\ge\cdots\ge a_1+2mc=(2m+1)c \] Then for all $n\ge mc+1$, where $n=qc+r$ and $1\le r\le c$, observe \[ a_{qc+r}\ge a_{(q-1)c+r}+2c\ge\cdots\ge a_{mc+r}+2(q-m)c \] \[ \ge a_{mc+1}+(r-1)+2(q-m)c\ge c+r-1+2qc\ge 2(qc+r)-1 \] So if $a_k=2k-1$ for some $k$, then equality holds throughout. In particular, because there are infinitely many such $k$, $a_{mc+1}=(2m+1)c$ for all nonnegative integer $m$, $r=c$, and \[ a_{mc+c}=a_{mc+1}+c-1=2mc+2c-1 \] so $a_{mc+r}=2mc+c+r-1$ for $1\le r\le c$. If $c>1$, then $a_2=c+1$, $a_c=2c-1$, and $a_{c+1}=3c$, a contradiction, so $c=1$, and \[ a_m=a_{(m-1)c+r}=2(m-1)+1+1-1=2m-1 \] Which clearly satisfies the conditions.

if $a_{k}<2k-1$ then $b$ is not satisfied. now if for all $i>k$ $a_{i}=2i-1$ then the sequence has no evens and $a_{i}=2i-1$ for all $i$. so if the sequence is not all odds there are infinitely many evens. if $n$ is the smallest with $a_{n}=2n-1$ we since $a_{n-1}\ge 2(n-1)-1$ then $a_{n-1}=2(n-1)$ easily giving (using b) that $a_{1},....,a_{n}$ are $n,n+1,.....,2n-1$ now if we choose some $x>n$ where $a_{x}$ is even and the minimum $h>x$ for which $a_{h}=2h-1$ we easily get $a_{h-1}=2(h-1)$ and $a_{1},..,a_{h}$ are $h,...,2h-1$ but $a_{1}=n<x<h=a_{1}$ giving a contradiction.

EDIT: This proof is wrong Assume that $a_i$ is even for some $i>2$. Then, $a_i\le 2i-1 \Rightarrow a_i \le 2i-2$. First we partition $2i-2$ as a sum of two positive integers (which can be done in $i-1$ ways). $$2i-2=1+2i-3$$$$\vdots$$$$2i-2=(i-1)+(i-1)$$ There can be at most $i-1$ pairs if $a_i\le 2i-2$ is expressed as a sum of two integers, and by condition one, we can have exactly one number from each pair among $a_1, a_2, \cdots a_{i-1}$; hence $a_i$ must equal $2i-2$ , since otherwise we would have both numbers from some pair, violating the first condition. Also note that no $a_j$ with $j<i$ can equal $i-1$, since then $a_j+a_j=a_i=2i-2$. Now, we can see above that $2i-2$ can be partitioned into exactly $i-1$ pairs , hence by the first condition, it is necessary that $a_1,\cdots a_{i-1}$ can take exactly one integer from each of the above pairs. But notice that the pair $(i-1, i-1)$ contains the number $i-1$ only. Hence, we cannot take any integer from this pair. So both numbers from some pair must appear in the sequence $a_1, a_2, \cdots a_{i-1}$. This is a contradiction. Hence, for every $i>2$, $a_i$ is odd. But since there exist infinitely many $i$ with $a_i=2i-1$, we infer that $a_k=2k-1$ for all $k>2$. Further, it is easy to see that $a_1=1, a_2=3$ since $a_2\le 3$ which leaves the following cases to consider: 1. If $a_1=1, a_2=2$, then $a_1+a_1=a_2$ violating the first condition of the problem. 2. If $a_1=2, a_2=3$ , then $a_1+a_2=a_3=5$ once again violating the first condition. Hence, $a_i=2i-1$ for all $i\ge 1$ is the only sequence satisfying the conditions of the problem.

The answer is only $a_k=2k-1$ for all $k$, which clearly works. Let $a_m=2m-1$ and $a_n=2n-1$, where $m<n$. Let $A=\{a_1,\ldots,a_m\}$ and $B=\{a_{m+1},\ldots,a_n\}$. Note that as the infinite sequence is sum-free, $B-A$ is does not intersect $A$ or $B$. Furthermore, the elements of $B-A$ are bounded above by $a_n-a_1\le 2n-1$ and below by $a_{m+1}-a_m\ge1$, so $B-A$ is a subset of $\{1,2,\ldots,2n-1\}$. We thus have that $|B-A|+|A|+|B|\le 2n-1$. However, recall that it is well-known that $|B-A|\ge|A|+|B|-1$, so we also have the lower bound $|B-A|+|A|+|B|\ge|A|+|B|-1+|A|+|B|=2(|A|+|B|)-1=2n-1$. This implies that equality must hold, i.e. $|A-B|=|A|+|B|-1$ so $A$ is an arithmetic sequence. Taking $m,n$ to be arbitrarily large implies the result.

math154 wrote: By (b) and symmetry, we have \[2k-1\ge \frac{|A_k-A_k|-1}{2}+|A_k|\] How is this inequality derived? I don't understand what's meant by $|A_k-A_k|$.

@gianteel In general, if you have two sets $A$ and $B$, then $\{a - b \mid a \in A, b \in B\}$ is denoted by $A-B$; in other words, its the set of all values you get from taking an element from $A$ and subtracting an element from $B$. This can be kind of confusing notation, especially when $A$ and $B$ are the same set, as in the case above. Here, math154 is counting the number of positive differences among elements of $A_k$ by taking $|A_k - A_k|$ then getting rid of $0$ (from taking $a - a$ for $a \in A_k$) and negative differences by dividing by $2$ (that's how he/she used symmetry). For clarity, if instead we call this set of positive differences $(A_k-A_k)^+$, then from condition $(b)$, $(A_k - A_k)^+$ and $A_k$ are disjoint, since otherwise $a-b = c \Rightarrow a = b+c$ is a solution. From condition $(a)$ the sequence is increasing, so each of $(A_k - A_k)^+$ and $A_k$ are contained in $\{1,2, \ldots, 2n-1\}$. Since they're disjoint: \begin{align*} 2k-1 &\ge |(A_k - A_k)^+ \cup A_k| = |(A_k - A_k)^+| + |A_k| \\ &\ge (k-1) + k = 2k-1 \end{align*}The second line comes from the fact that $A_k$ has $k$ elements and $(A_k-A_k)^+$ contains at least the $k-1$ distinct elements $a_k - a_{k-1}, a_k - a_{k-2}, \ldots, a_k - a_1$. Since this turns out to be an equality, $|(A_k - A_k)^+| = k-1$ exactly.

this means that $a_1, a_2, \ldots, a_k$ are in an arithmetic progression. So from condition $(c)$, we can keep taking larger and larger values of $k$ so that $a_k = 2k-1$ to show that the sequence up to that $k$ is arithmetic, so that the entire sequence is. Now take $r < s$ so that $a_r = 2r-1$ and $a_s = 2s-1$, which determines the arithmetic progression as being the sequence of all odd positive integers (in order).

We claim $a_i=2i-1$ for all $i\ge 1$. Choose some $n$ with $a_n=2n-1$. We will show that $a_k=2k-1$ for all $k\le n$. Let $A=\{a_1,\ldots,a_n\}$. Let $D=\{a_i-a_j : 1\le i < j \le n\} = |A-A|$. We know $A$ is disjoint from $\{a_1,\ldots,a_n\}$. Also, all the elements of $A$ and of $D$ are positive integers at most $2n-1$. This imposes severe size restrictions. Indeed, it is well-known that $|D| = |A-A| \ge 2|A|-1=2n-1$. However, if we only include positive elements of $A-A$, by symmetry we will have at least $\lfloor (2n-1)/2 \rfloor =n-1$ elements. Since there are exactly $2n-1$ spaces for positive integers from $2n-1$ to 1, we get that equality is achieved in our estimate $|A-A| \ge 2n-1$. It is well-known that this implies $A$ is an arithmetic sequence. The only way for this to hold for all the infinitely many $n$ with $a_n=2n-1$ is if $a_k=2k-1$ for all $k\ge 1$.

Originally didn't seem too keen to post a Solution to this problem; however, I think that this problem illustrates how doing something similar before (here and here) on difference sets makes the absurd condition \[\begin{tabular}{p{12cm}} [$a_k = 2k-1$ for infinitely many $k$] \end{tabular} \\ \]much more bearable and analyze-able (while not being exact copies of the aforementioned problems, of course ...) $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Here We Go, with the One-Liners.}$ First, we prove that $a_1 = 1$. If not, let $a_1 = c$. Pick an index $k$ so that $a_k = 2k-1$. Now consider the set \[S = \{1,2,\ldots,c-1\} \, \cup \, \{a_1,a_2,\ldots,a_k\} \, \cup \, \{c+a_1,c+a_2,\ldots,c+a_{k-c}\}\]Then, analyzing the members of these sets, we can infer that They do not intersect each other; in fact, since each integer $a_i$ $i \geq 1$ is at least $c$, the members of the second set and the third set are strictly greater than the members of the first set, and the second/third set do not intersect each other due to the second condition of the problem. Most importantly, they are all less than or equal to $2k-1$: since $a_{k-c} \leq a_k - c = 2k+1-c$, all the terms $a_1+a_i$, $i \leq k-c$ satisfies $a_1+a_i \leq 2k-1$. So, the set $S$ is equal to the set $\{1,2,\ldots,2k-1\}$. With that in mind, if $c \ne 1$, since all the members of the second set are at least $c+c = 2c$, all the numbers \[ c,c+1,\ldots,2c-1\]must be a member of the second set; i.e. we have the property \[ a_1 = c, a_2 = c+1, \ldots, a_{c-1} = 2c-1 \]Because of that, $a_2 + a_{c-1} = 3c \not\in \{a_1,a_2,\ldots,a_k\}$; or it would contradict the second statement. So, that number must exist in the third set, it means that there exists an index $i \leq k-c$ so that $a_i = 3c-c = 2c$. This immediately yields a contradiction. $\blacksquare$ $\blacksquare$ $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Initial term go brrrr.}$ We will prove by induction that $a_n = 2n-1$ for each $n \in \mathbb{N}$. Let the statement to be true for $n = i$. Now select a $k \geq i+1$ so that $a_k = 2k-1$ and construct $S_k$ as above (but with $k$ sliding through pass $i+1$). Since $S_k$ is the union of sets $\{a_1,a_2,\ldots,a_k\}$ and $\{1+a_1,\ldots,1+a_{k-1}\}$, the number $2i \leq 2k-1$ belongs to the second set, as $1+a_i = 1+(2i-1) = 2i$ --- or we can also say that if $a_{i+1}$ (the least term which is greater than $a_i = 2i-1$) is equal to $2i$, the problem condition is dissatisfied. As a result, $2i+1$ is not an element of the second set; or that would imply that there exists an index $j$ so that $a_1 + a_j = 2i+1$, or $a_j = 2i$. So, $2i+1$ is part of the set $\{a_1,a_2,\ldots,a_k\}$, meaning that the next bigger term after $a_i$ will need to have value $2i+1$. This will imply that $a_{i+1} = 2i+1 = 2(i+1)-1$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Let $a_k= 2k-1,a_l=2l-1$ for two arbitrarily large $k<l.$ Then, let $A=\{a_1,a_2,\dots,a_k\}$ and $B=\{a_{k+1},a_{k+2},\dots,a_l\}.$ Let $C$ be all the possible differences between elements of $B$ and $A.$ Then, $A,B,C$ are pairwise disjoint and $\max{(A\cup B\cup C)}=a_l=2l-1.$ Thus, we have \[l+|C|=|A|+|B|+|C|=|A\cup B\cup C|\le 2l-1.\]This implies that $|C|\le l-1.$ However, the following $l-1$ elements of $C$ are all distinct: $a_{k+1}-a_k, a_{k+2}-a_k,\dots a_{l-1}-k, a_l-a_k, a_l-a_{k-1},\dots, a_l-a_2,a_l-a_1.$ From this, it follows that $A,B$ both form arithmetic sequences, and that $\min{(A\cup B\cup C)}=1.$ These two conditions together implies that $a_i=2i-1$ for all $i\le l.$ Take $l$ to infinity and we have $a_i=2i-1$ for all integers $i.$ (edit: dude why is that 2i-1 massive)

Let $a_1=s$ , firstly we'll show that for each natural number $k \in \mathbb{N}$ we have $a_{k+s}-a_{k} \ge 2s$. Suppose not and $a_{k+s} \le a_{k}+2s-1$ , note that there doesn't exist index $i$ such that $a_i=a_k+s$ ( because otherwise , we have $a_k+a_1=a_i$ which is a contradiction. ) so numbers $a_{k+1} , a_{k+2} , ... , a_{k+s}$ are $s$ distinct values in $a_k+1 , a_k+2 , ... , a_{k}+2s-1$ which by pigeonhole principle there exist $1 \le i<j \le s$ that $a_i+s=a_j$ which is a contradiction again. Now note that for each $i \le s$ one can see that : $$a_i \ge i+s-1 \ge 2i-1 , a_{k+s} \ge a_{k}+2s \ge 2(k+s)-1$$So for each $i \in \mathbb{N}$ we have $a_i \ge 2i-1$ and obviously equality can hold only for each index $s|i$. Now note that if for a natural number $k$ we have $a_{sk} > 2sk-1$ , then by $a_{l+s}-a_l \ge 2s$ , for each number $l \ge k$ we can get $a_{sl} > 2sl-1$ and thus , the equality $a_i=2i-1$ holds for finitely many values if $i$ , which is a contradiction. So for each $k \in \mathbb{N}$ we have $a_{sk}=2sk-1$. So while $a_1=s$ and $a_s=2s-1$ and the sequence is strictly increasing , for each $i \le s$ we get $a_i=i+s-1$ and also $a_{2s}=4s-1$ , $a_{s+1} \ge a_1+2s=3s$ and as the result $a_{s+1}=3s$. So if $s \ge 2$ , then we have $a_2=s+1$ and $a_2+a_s=a_{s+1}$ which is a contradiction. As the result , $s=1$ and for each $k \in \mathbb{N}$ , $a_k=2k-1$. So we're done.

alexiaslexia wrote: Originally didn't seem too keen to post a Solution to this problem; however, I think that this problem illustrates how doing something similar before (here and here) on difference sets makes the absurd condition \[\begin{tabular}{p{12cm}} [$a_k = 2k-1$ for infinitely many $k$] \end{tabular} \\ \]much more bearable and analyze-able (while not being exact copies of the aforementioned problems, of course ...) $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Here We Go, with the One-Liners.}$ First, we prove that $a_1 = 1$. If not, let $a_1 = c$. Pick an index $k$ so that $a_k = 2k-1$. Now consider the set \[S = \{1,2,\ldots,c-1\} \, \cup \, \{a_1,a_2,\ldots,a_k\} \, \cup \, \{c+a_1,c+a_2,\ldots,c+a_{k-c}\}\]Then, analyzing the members of these sets, we can infer that They do not intersect each other; in fact, since each integer $a_i$ $i \geq 1$ is at least $c$, the members of the second set and the third set are strictly greater than the members of the first set, and the second/third set do not intersect each other due to the second condition of the problem. Most importantly, they are all less than or equal to $2k-1$: since $a_{k-c} \leq a_k - c = 2k+1-c$, all the terms $a_1+a_i$, $i \leq k-c$ satisfies $a_1+a_i \leq 2k-1$. So, the set $S$ is equal to the set $\{1,2,\ldots,2k-1\}$. With that in mind, if $c \ne 1$, since all the members of the second set are at least $c+c = 2c$, all the numbers \[ c,c+1,\ldots,2c-1\]must be a member of the second set; i.e. we have the property \[ a_1 = c, a_2 = c+1, \ldots, a_{c-1} = 2c-1 \]Because of that, $a_2 + a_{c-1} = 3c \not\in \{a_1,a_2,\ldots,a_k\}$; or it would contradict the second statement. So, that number must exist in the third set, it means that there exists an index $i \leq k-c$ so that $a_i = 3c-c = 2c$. This immediately yields a contradiction. $\blacksquare$ $\blacksquare$ $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{Initial term go brrrr.}$ We will prove by induction that $a_n = 2n-1$ for each $n \in \mathbb{N}$. Let the statement to be true for $n = i$. Now select a $k \geq i+1$ so that $a_k = 2k-1$ and construct $S_k$ as above (but with $k$ sliding through pass $i+1$). Since $S_k$ is the union of sets $\{a_1,a_2,\ldots,a_k\}$ and $\{1+a_1,\ldots,1+a_{k-1}\}$, the number $2i \leq 2k-1$ belongs to the second set, as $1+a_i = 1+(2i-1) = 2i$ --- or we can also say that if $a_{i+1}$ (the least term which is greater than $a_i = 2i-1$) is equal to $2i$, the problem condition is dissatisfied. As a result, $2i+1$ is not an element of the second set; or that would imply that there exists an index $j$ so that $a_1 + a_j = 2i+1$, or $a_j = 2i$. So, $2i+1$ is part of the set $\{a_1,a_2,\ldots,a_k\}$, meaning that the next bigger term after $a_i$ will need to have value $2i+1$. This will imply that $a_{i+1} = 2i+1 = 2(i+1)-1$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Why does $3c$ exist in $S$?

not cool like some of the above solutions, but pretty natural i think