One can find $a_i, a_j, a_k$ sides of a triangle among a certain sequence $a_1, ..., a_{2n+1}$ where $1
Suppose $a_1, a_2, ..., a_{2n+1}$ are distinct positive integers so that $1<a_i<2^n$ for all $1\leq i\leq2n+1$, show that there exists $a_i, a_j, a_k$ ($1\leq i<j<k\leq2n+1$) so that they are the sides of a triangle.
This is my attempt to this problem:
WLOG, suppose $a_1<a_2<...<a_{2n+1}$. We have to prove that $a_i+a_j>a_k$ , $a_i+a_k>a_j$, $a_j+a_k>a_i$. Since $i<j<k$, we can obviously see that $a_i+a_k>a_j$ and $a_j+a_k>a_i$ because $a_k>a_i$ and $a_j$. So the problem reduces to showing that there are $i,j,k$ so that $a_i+a_j>a_k$.
This is a problem related to the Pigeonhole principle, so I suppose I need to find a way to make the "containers" and "pigeons". I tried to work around the $2^n$ tight bound, but didn't quite get the answer. One more thing I found is that we can safely say we only need to find 3 consecutive numbers, since it will maximize $a_i+a_j$ and minimize $a_k$, but I can't quite figure out what to do with that.
I would appreciate a hint to this problem and thank you.
Edit: I found an answer using the Pigeonhole principle:

Since we have $2n+1$ numbers and $1\leq a_i<2^n$, we can put 3 numbers into $n$ "containers": $[2^0, 2^1), [2^1, 2^2), [2^2, 2^3), ..., [2^{n-1}, 2^n)$. Assume $a_x, a_y, a_z\in[2^k, 2^{k+1})$, $0\leq a_x<a_y<a_z\leq n-1$. Then we have $a_x+a_y\geq2^k+2^k=2^{k+1}>a_z$. The case of $a_z+a_y>a_x$ and $a_z+a_x>a_y$ are trivial.

 A: Proceed by contradiction, assume every value is in range $(1,2^n)$ and there is no triangle. One has $a_1\geq 1$ and $a_2\geq 1$ and by induction one has $a_{m+2}\geq a_{m} + a_{m+1}$ for every $m$ if there is no triangle with $a_m,a_{m+1},a_{m+2}$. It follows one has $a_m \geq f_{m}$ for every $m$, where $f_m$ is the usual fibonacci sequence, however we can show $f_{2n+1} \geq 2^n$ by induction. The case $n=0$ holds with equality.
For the inductive step we have $f_{2(n+1)+1} = f_{2n+1} + f_{2n+2} \underbrace\geq_{\hspace{-1cm}\text{induction hypothesis}\hspace{-1cm}} 2^n + 2^n \geq 2^{n+1}$.
We have reached a contradiction as $a_{2n+1} \geq 2^n$.
A: Similar to @Yorch answer, but no Fibonacci involved ...
As you mentioned, it is sufficient to find a triplet $$a_i+a_{i+1}> a_{i+2}$$
Now, let's assume there is no such triplet, i.e. (wlog assumption) for all $i$
$$2a_i<a_i+a_{i+1}\leq a_{i+2}$$
or
$$2a_{2n-1}< a_{2n+1}$$
$$2^2 \cdot a_{2n-3}< 2a_{2n-1}< a_{2n+1}$$
$$2^3 \cdot a_{2n-5}< 2^2 \cdot a_{2n-3}< 2a_{2n-1}< a_{2n+1}$$
or, by induction
$$2^j\cdot a_{2n+1-2j}< ...< a_{2n+1}$$
and
$$2^n <2^n \cdot a_1< ...< a_{2n+1}$$
which is a contradiction.
