summation - Sum of Term plus Sum of Terms so far Proof

I've been given a homework question (so feel free to prod me in the right direction, as opposed to giving a fully worked answer) that ask me, in essence, the following question.

Given a series of $ n $ integers, $ S $, prove that the minimum value of

$ C(S) = S_1 + (S_2 + S_1) + ... +(S_n + S_{n-1} + ... + S_1) = \sum_{i=1}^n{(n+1-i) \times S_i} $

is when $ S $ is sorted in ascending order.

I'm using the following definition of "sorted in ascending order":

$ \forall i,j $ s.t. $ 1 \le i \lt n, j > i, S_i \le S_j $

So I feel like it's the sort of problem where I should be using induction.

The base case is pretty trivial.

For $ n = 2 $, $ S $ has an ordering of $ S = [S_1, S_2]$. If there's some different ordering of $ S $, $ T $ that is lower cost than $ S $, it must be ordered $ T = [ S_2, S_1 ] $ with a cost $ C(T) = 2S_2 + S_1 $. If it's a lower cost:

$ C(T) \lt C(S) $

$ 2S_2 + S_1 \lt 2S_1 + S_2$

$ S_2 < S_1 $, but we know $S_1 \le S_2 $ so there's a contradiction and the base case is proven.

At this point, sort of hit a wall. I have that:

For $n = k$, $ C(S) = \sum_{i=1}^k{(k+1 -i) S_i} $

And, for $ n = k + 1 $, $C(S) = \sum_{i=1}^{k+1}{(k+2 -i) S_i} $

$ C(S) = \sum_{i=1}^k{(k+1 -i) S_i} + S_{k+1} + \sum_{i=1}^k{S_i} $

So I think I need to show something along the lines that $ S_{k+1} + \sum_{i=1}^k{S_i} $ is the optimum final move or something, but I can't think of how to do that.

I'm also not sure if induction is even the way to go. Would there be a better way of proving this? Any help you can give would be appreciated.

Answer

There are other ways to go about this, but induction is a perfectly good one. You're so, so close!

Hint: The punch line at the end of the proof is not to show that $S_{k+1} = \sum_{i=1}^k S_i$, also known as $\sum_{i=1}^{k+1} S_i$, is optimal. That expression is just the sum of all the terms, so it will appear in the final summation now matter how the terms are arranged. Instead, your task is to argue why the $\sum_{i=1}^k (k+1-i) S_i$ part of that same line is optimal.