Show: For any $n+1$ integers chosen from $[1,2n-1]$, there are $3$ numbers chosen such that the sum of two of them gives us the third number

Question

Let $n$ be a positive integer, and let $S$ be a set of $n+1$ integers in $[1,2n-1]$. Then show that there are $3$ numbers in $S$ such that the sum of two of them gives us the third number (the numbers chosen are not necessarily consecutive).'

For example, for $n=3$, then note that, given any set $S$ of $4$ numbers in the set $\{1,2,3,4,5\}$, there two numbers in $S$ that give us the sum of another number in $S$. e.g., if $S=\{1,2,4,5\}$, then $1+4=5$, with all three numbers $1,4,5$ in $S$.

Answer 1

We prove by induction. The base case of $n = 2$ follows since the only set is $\{1, 2, 3\}$.

Suppose it is true for $n - 1$. Now we tackle the $n$ case. If we did not choose $2(n - 1) + 1$, then we chose at least $n$ numbers less than $2(n - 1)$ so we are done by inductive hypothesis. Otherwise by pigeon hole principle, there must exitst some $1 \leq k \leq n - 1$ such that we chose both $k$ and $2(n - 1) + 1 - k$. So we are done.

Answer 2

Let $a$ be the smallest number in $S$. Then every remaining number in $S$ is at least $a+1$ and no larger than $2n-1$. Thus, there are $n$ integers $x$ in the interval $[2a+1,2n+a-1]$ of the form $x=a+b$; $b \in S \setminus \{a\}$. Thus, by the Pigeonhole Principle, the set $T$ of integers $x=a+b$; $b \in S \setminus \{a\}$; $x$ in the interval $[2a+1,2n-1];$ has at least $n-a$ integers. [Make sure you see why]

On the other hand, also by the Pigeonhole Principle, the set $U$ of integers $y \in S$ satisfying $y \ge 2a+1$, or equivalently, $y$ in the interval $[2a+1,2n-1]$, is at least than $n-a$. [Make sure you see why]

So to finish, it suffices to show that $T$ and $U$ intersect. [Make sure you see why.] However, both $T$ and $U$ are subsets of the set of integers in $[2a+1,2n-1]$, which has exactly $2n-2a-1$ integers. Yet $$|T|+|U| \ge (n-a)+(n-a)$$ $$=2n-2a > 2n-2a-1.$$ Can you finish from here.

NOTE THAT if $2n$ is allowed to be in $S$ i.e., if $S$ were allowed to be any set of $n+1$ integers in $[1,2n]$, then the result no longer holds. Take $S =\{n,n+1,\ldots, 2n\}$. Likewise, if $S$ is allowed to have $0$, i.e., if $S$ were allowed to be any set of integers in $[0,2n-1]$: Take $S=\{n,n+1,\ldots, 2n-1,0\}$.