# How to prove the minimum identity for finite number of real numbers

I have trouble in proving the following statement: Let $n$ be an integer no less than 3, and $a_1,\dots, a_n$ be real numbers. If $n$ is even, then \begin{align*} &\min\{a_1,a_2,a_3\}+\min\{a_1,a_2,a_4\}+\cdots +\min\{a_{n-2}, a_{n-1},a_n\}\\ &+\min\{a_1,\dots, a_5\}+\min\{a_2,\dots, a_6\}+\cdots+\min\{a_{n-4},\dots, a_n\}\\ &+\cdots +\min\{a_1,\dots, a_{n-1}\}+\cdots +\min\{a_2,\dots, a_n\}\\ &+\min\{a_2+\cdots+a_n, a_1+\widehat{a_2}+\cdots +a_n,\dots, a_1+\cdots +a_{n-1}+\widehat{a_n}\}\\ =&\min\{a_1,a_3\}+\min\{a_1,a_4\}+\cdots+\min\{a_{n-1},a_n\}\\ &+\min\{a_1,\dots, a_4\}+\min\{a_1,a_2,a_3,a_5\}+\cdots +\min\{a_{n-3},\dots, a_n\}\\ &+\cdots+\min\{a_1,\dots, a_{n}\},\tag{1} \end{align*} where the notation $\widehat{a_2}$ means that number $a_2$ is deleted. If $n$ is odd, then \begin{align*} &\min\{a_1,a_2,a_3\}+\min\{a_1,a_2,a_4\}+\cdots +\min\{a_{n-2}, a_{n-1},a_n\}\\ &+\min\{a_1,\dots, a_5\}+\min\{a_2,\dots, a_6\}+\cdots+\min\{a_{n-4},\dots, a_n\}\\ &+\cdots +\min\{a_1,\dots, a_n\}\\ &+\min\{a_2+\cdots+a_n, a_1+\widehat{a_2}+\cdots +a_n,\dots, a_1+\cdots +a_{n-1}+\widehat{a_n}\}\\ =&\min\{a_1,a_3\}+\min\{a_1,a_4\}+\cdots+\min\{a_{n-1},a_n\}\\ &+\min\{a_1,\dots, a_4\}+\min\{a_1,a_2,a_3,a_5\}+\cdots +\min\{a_{n-3},\dots, a_n\}\\ &+\cdots+\min\{a_1,\dots, a_{n-1}\}+\cdots+\min\{a_2,\dots, a_n\}.\tag{2} \end{align*} For instance, if $n=5,$ then \begin{align*} &\min\{a_1,a_2,a_3\}+\min\{a_1,a_2,a_4\}+\min\{a_1,a_2,a_5\}+\min\{a_1,a_3,a_4\}\\ &+\min\{a_1,a_3,a_5\}+\min\{a_1,a_4,a_5\}+\min\{a_2,a_3,a_4\}+\min\{a_2,a_3,a_5\}\\ &+\min\{a_2,a_4,a_5\}+\min\{a_3,a_4,a_5\}+\min\{a_1,\dots, a_5\}\\ &+\min\{a_2a_3a_4a_5,a_1a_3a_4a_5,a_1a_2a_4a_5,a_1a_2a_3a_5,a_1a_2a_3a_4\}\\ =&\min\{a_1,a_2\}+\min\{a_1,a_3\}+\min\{a_1,a_4\}+\min\{a_1,a_5\}+\min\{a_2,a_3\}\\ &+\min\{a_2,a_4\}+\min\{a_2,a_5\}+\min\{a_3,a_4\}+\min\{a_3,a_5\}+\min\{a_4,a_5\}\\ &+\min\{a_1,a_2,a_3,a_4\}+\min\{a_1,a_2,a_3,a_5\}+\min\{a_1,a_2,a_4,a_5\}\\ &+\min\{a_1,a_3,a_4,a_5\}+\min\{a_2,a_3,a_4,a_5\},\tag{3} \end{align*} while if $n=4,$ then \begin{align*} &\min\{a_1,a_2,a_3\}+\min\{a_1,a_2,a_4\}+\min\{a_1,a_3,a_4\}+\min\{a_2,a_3,a_4\}\\ &+\min\{a_2a_3a_4, a_1a_3a_4, a_1a_2a_4,a_1a_2a_3\}\\ =&\min\{a_1,a_2\}+\min\{a_1,a_3\}+\min\{a_1,a_4\}+\min\{a_2,a_3\}\\ &+\min\{a_2,a_4\}+\min\{a_3,a_4\}+\min\{a_1,\dots,a_4\}.\tag{4} \end{align*} Since (3) and (4) are both transpositionally symmetrical, and cyclically symmetrical, it is easy to prove (3) and (4), by just considering the case that $a_1\leq a_2\leq \cdots \leq a_5.$ But it is not so for (1) and (2). Who can help me? Or is there easier proof of (1) and (2)? I want to use these identities to prove an identity of GCD in elementary number theory, that is, \begin{gather*} \gcd\left(a_2a_3\cdots a_n, a_1a_3\cdots a_n,\dots, a_1\cdots a_{n-1}\right)=\cdots. \end{gather*}

• I feel like there could be an interesting question here but it is drowning in ellipses! Is there a high-level description you can give for which terms belong to the LHS and RHS? – Erick Wong Feb 28 '18 at 2:51
• What's the full identity of gcd you're proving? – Saad Feb 28 '18 at 3:05
• So this is the sum of the minimum of all odd subsets? – fleablood Feb 28 '18 at 3:10
• @AlexFrancisco: If we can prove (1) and (2), then, by FTA(Fundamental Theorem of Arithmetic), the RHS can be given suddenly. I just write the four-number case: $\gcd(ab,bc,ca)\gcd(a,b,c)=\gcd(a,b)\gcd(a,c)\gcd(b,c).$ – azc Feb 28 '18 at 3:25