Minimizing result that depends on the order of number choices Question.
Let $n$ be a positive integer. Write $1, 2, ..., n$ on a paper. Each round you may pick two numbers $m, n$ from the paper, erase them and write a new number $2(m+n)$ on the paper.
Prove that the final number on the paper is always greater than $\frac{4}{9}n^3$.

I saw people approach this problem by induction on $n$. They claimed that to minimize the result you have to put the greatest number in the end. Assume that the hypo holds for $k$, then
$$\text{(all possible result of 1 to k+1)} \geq 2[\frac{4}{9}k^3 + (k+1)] \geq \frac{4}{9}(k+1)^3 \text{ , for $k$ big enough.}$$
The rest is to verify the problem also holds for finite $k$ dissatisfying the inequality above.

My instinct told me the claim is wrong. Soon I found a counterexample. Take $n=4$, result of the method $1, 2 \to 6; 3, 4 \to 14; 6, 14 \to40$ is less than $1, 2 \to 6; 3, 6 \to 18; 18, 4 \to 44$. Hence the proof above does not work.
I also do not have other ways to approach the question. What else can I try? Any help is appreciated.
 A: This shows for a weaker $\frac{1}{4} n^3$.
I'm not sure if this can be strengthened to show $ \geq \frac{4}{9} n^3$. We did relax several of the constraints.
Hopefully the ideas here can spur you on.
It seems unlikely that $ \sum 2^{c_i} i \geq \frac{16}{9} n^2$.

For the number that's written on the paper, let's not evaluate $ 2(m+n)$, but instead write it as $2m+ 2n$. Continue till we have a final expression.
EG using OP's construction for $n = 4$ gives
$$ 2( 2(1+2) + 2(3+4) ) = 2^2 \times 1 + 2^2 \times 2 + 2^2 \times 3 + 2^3 \times 4 . $$
This shows us how the total sum can be written as $S_n = \sum_{i=1}^n 2^{a_i} i $.
For each sequence, let $ \alpha_n = \sum a_i$ , and let $A_n = \min \alpha_n$ taken over every sequence for $n$.
Idea: If we have control over $A_n$, then we some have control over $ S_n$.
Let $B_n $ be the Binary Entropy Function given by $B_1 = 0, B_n = n+ \min_{1 \leq k \leq n-1 } B_k + B_{n-k}$.
Lemma: $A_n = B_n$.
Proof: This easily follows by induction: The base case holds, and $A_n = n + \min_{1 \leq k \leq n-1 } A_k + A_{n-k}$ by considering the last $2(m+n)$ term.
Lemma: $B_n \geq  n (\log_2 n)$
Proof: This follows by strong induction.
Observe that $f(x) = x \log_2 x $ is convex on $x \geq 1$ as $f''(x) = \frac{1}{n \log 2 }$, so
$B_n \geq n + 2 \times ( n/2) \log_2 (n/2) = n\log_2 n$
Note: I suspect that $ B_n = n \log_2 n $ for $n = 2^k$. At least it does for $k = 1, \ldots 15$.
Now that we have a bound of $\sum a_i$, how can we minimize $ \sum 2^{a_i} i $?
If we consider this incrementally, we will want to increase the smallest $ 2^{a_i} \times i $ term to $ 2^{a_i + 1 } \times i$, until we reach the total desired sum. When there are 2 values $ 2^{a_i} i = 2^{a_j} j$, we can agree to increase $a_i$ for the the larger $i$ index.
For example, with $A_8 = 4$, the minimum sum is $ \sum 2^2 \times 1 + 2^2 \times 2 + 2^2 \times 3 + 2^2 \times 4 = 14$
For a fixed $n$, let's see how much we need to increase each term to between $n$ and $2n-1$ inclusive. Let $ c_i$ denote the unique integer such that $ n \leq 2^{c_i} \times i < 2n $.  Let $ \sum c_i = C_n$.
Claim: $C_n \leq 2n$.
Proof: By strong induction.
For $n = 2m$,  $C_{2m} = C_m + (2m-1) \leq 2m+(2m-1) \leq 2(2m)$.
For $n = 2m+1$, $C_{2m+1} = C_{m+1} + 2m \leq 2(m+1) +2m = 2(2m+1)$.
Corollary: $\sum 2^{a_i} \times i = \sum 2^{a_i - c_i} \times 2^{c_i} \times i \geq n \sum 2^{a_i - c_i } \geq n \times n \times 2^{\frac{ A_i - C_i } { n } } = \frac{n^3}{4}$.

Other comments, but these don't seem that useful.

*

*Lemma: If $\sum 2^{a_i} i $ can be achieved, then so can $ \sum_{\sigma \in S_n } 2^{a_i} \sigma (i)$.
Proof: There is nothing unique about the $i$ values, and we can apply any permutation to them.


*Lemma: In the minimal sum, $ a_1 \geq a_2 \geq \ldots \geq a_n$.
Proof: If for some $ i  < j, a_i < a_j$, then permuting $i$ and $j$ allows us to decrease the sum further.
