Here’s the problem. Given two non-decreasing sets of $n$ real numbers, $a_1 \leq \cdots \leq a_n$ and $b_1 \leq \cdots \leq b_n$. Define $$Q(\ell_1, \cdots , \ell_n) = \sum_{i=1}^n (a_i - b_{\ell_i})^2$$ where $\{\ell_1, \cdots , \ell_n\}$ is a permutation of $\{1, \cdots , n\}$.Show that $$Q(\ell_1, \cdots , \ell_n) \geq Q(1, \cdots , n)$$
The base case is trivial, but what’s difficult is being able to use the induction hypothesis (IH) to prove that the $n=N$ case implies the $n=N+1$ one. ($N \geq 1$) My suspicion is that I need a key step related to the two sets of non-decreasing reals, but I can’t quite think of one. Here’s one attempt that comes the closest so far.
We have $$Q(\ell_1, \cdots , \ell_N, \ell_{N+1})=(a_k - b_{N+1})^2 + \sum_{\substack{i=1 \\ i \neq k}}^{N+1} (a_i - b_{\ell_i})^2$$ Where $k$ is the index such that $\ell_k = N+1$. If $k=N+1$, we can easily use the IH to get our desired result. Otherwise let $k \leq N$. The plan is to manipulate our terms such that we can have $Q(\ell_1, \cdots , \ell_N)$ somewhere in our expression and thus can use the IH and then do some more manipulation to get our result.
Here’s how it looks like \begin{align} Q(\ell_1, \cdots , \ell_N, \ell_{N+1}) & =(a_k - b_{N+1})^2 + \sum_{\substack{i=1 \\ i \neq k}}^{N+1} (a_i - b_{\ell_i})^2 \\ & =(a_k - b_{\ell_k})^2 + 2a_kb_{\ell_k} - 2a_kb_{N+1} + b_{N+1}^2 -b_{\ell_k}^2 + \sum_{\substack{i=1 \\ i \neq k}}^{N+1} (a_i - b_{\ell_i})^2 \\ & =2a_kb_{\ell_k} - 2a_kb_{N+1} + b_{N+1}^2 -b_{\ell_k}^2 + (a_{N+1} - b_{\ell_k})^2 + \Bigl( (a_k - b_{N+1})^2 + \sum_{\substack{i=1 \\ i \neq k, N+1}}^{N+1} (a_i - b_{\ell_i})^2 \Bigr) \end{align}
Now notice that if we remove $\ell_k$ from $\{\ell_1, \cdots , \ell_{N+1} \}$, the remainding set would be a permutation of $\{1, \cdots , N\}$ since now $\ell_{N+1}$ would be between $1$ and $N$ inclusive and we’ve removed $\ell_k = N+1$. We can rename our set without $\ell_k$ as $\{\sigma_1, \cdots , \sigma_N\}$. So using the IH we have \begin{align} & 2a_kb_{\ell_k} - 2a_kb_{N+1} + b_{N+1}^2 -b_{\ell_k}^2 + (a_{N+1} - b_{\ell_k})^2 + \Bigl( (a_k - b_{N+1})^2 + \sum_{\substack{i=1 \\ i \neq k, N+1}}^{N+1} (a_i - b_{\ell_i})^2 \Bigr) \\ = & 2a_kb_{\ell_k} - 2a_kb_{N+1} - 2a_{N+1}b_{\ell_k} + b_{N+1}^2 + a_{N+1}^2 + \sum_{i=1}^{N} (a_i - b_{\sigma_i})^2 \\ \geq & 2a_kb_{\ell_k} - 2a_kb_{N+1} - 2a_{N+1}b_{\ell_k} + b_{N+1}^2 + a_{N+1}^2 + Q(1, \cdots , N) \end{align}
And this is where I’m stuck.
Let's simplify things. Note that $$Q(\ell) = \Big(\sum_i a_i^2+b_{\ell_i}^2\Big)-2\sum_{i}a_ib_{\ell_i},$$ and the first summation is the same for every $\ell$. Therefore, we may show that the quantity $$ \tilde Q(\ell)=\sum_{i}a_ib_{\ell_i} $$ is maximized when $\ell$ is the identity permutation.
To prove this, suppose that $\ell$ has an inversion, meaning a pair $(i,j)$ where $i<j$ but $\ell_i>\ell_j$. Note that this implies $(a_j-a_i)(b_{\ell_i}-b_{\ell_j})\ge 0$, so that $$ a_ib_{\ell_j}+a_jb_{\ell_i}\ge a_ib_{\ell_i}+a_jb_{\ell_j}\tag{1} $$ Now, consider what happens when you make a new permutation $\ell'$, which is just like $\ell$ except that $\ell_i$ and $\ell_j$ are switched. According to $(1)$, this means that $\tilde Q(\ell')\ge \tilde Q(\ell)$, because the sum of the two affected products has increased. Therefore, any permutation with an inversion is weakly dominated by one with fewer inversions,${}^*$ so the identity permutation (the only permutation without any inversions) is maximal.
${}^*$I am skipping over the detail of proving that $\ell'$ has fewer inversions than $\ell$. This takes a little thought to prove. Alternatively, to any permutation $\ell$ you can associate the quantity $E(\ell)=\sum_i i\ell_i$, and show that $E(\ell')>E(\ell)$ using the same method. Since this quantity cannot increase forever, performing enough "un-inversions" will eventually create a permutation with no inversions.