1
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Erick Wong Feb 28 '18 at 2:51
  • $\begingroup$ What's the full identity of gcd you're proving? $\endgroup$ – Saad Feb 28 '18 at 3:05
  • $\begingroup$ So this is the sum of the minimum of all odd subsets? $\endgroup$ – fleablood Feb 28 '18 at 3:10
  • $\begingroup$ @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).$ $\endgroup$ – azc Feb 28 '18 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.