$n_1^3 + n_2^3 + ... + n_k^3 \geq (n_1 +n_2 + ...+ n_k)^2$ for natural numbers $n_1 < n_2 < ... < n_k$ Prove that for natural numbers $n_1 < n_2 < ... < n_k$:
$$n_1^3 + n_2^3 + ... + n_k^3 \geq (n_1 +n_2 + ...+ n_k)^2$$
I have no idea how to do that. I would go for induction, but there is an infromation that $n_1 < n_2 < ... < n_k$ and induction would not recognise that fact.
What's funny is that I think I saw once that exercise on stack exchange but wasn't able to find it this time.
 A: With (double) induction on $k$. Notice that $n_i^3\geq n_i^2\cdot i$ for all $i$.
If $k=1$ the we have $n_1^3\geq n_1^2$ which is true.
Suppose it is true for $k$:
$$n_1^3 + n_2^3 + ... + n_k^3 \geq (n_1 +n_2 + ...+ n_k)^2$$
and we prove it for $k+1$:
\begin{align}n_1^3 + n_2^3 + ... + n_k^3 +n_{k+1}^3 &\geq (n_1 +n_2 + ...+ n_k)^2 + n_{k+1}^3\\\end{align}
We have to check if $$(n_1 +n_2 + ...+ n_k)^2 + n_{k+1}^3 \geq (n_1 +n_2 + ...+ n_{k+1})^2 $$ i.e. $$n_{k+1}^3 \geq 2(n_1 +n_2 + ...+ n_k)n_{k+1}  +n_{k+1}^2 $$ i.e.  $$n_{k+1}(n_{k+1}-1) \geq 2(n_1 +n_2 + ...+ n_k) \;\;\;(*)$$ is true.
Now this $(*)$ can be separately proved again by induction: Since $n_{k+1}\geq n_k+1$ we have $$n_{k+1}(n_{k+1}-1) \geq n_k(n_k+1) = n_k^2+n_k$$ so it is enough to prove $$n_k^2+n_k\geq 2(n_1 +n_2 + ...+ n_k) $$  i.e. $$n_k^2-n_k\geq 2(n_1 +n_2 + ...+ n_{k-1}) $$
which is again true by induction asumption.
A: I have a proof without induction. It's not as elegant as the induction proof but some of the results might be of interest to you. The proof is long but there's very little calculation.

Suppose we fix the sum of $n_j$'s and we want to minimize the sum of cubes. Because there are finite number of $k$-tuples $(n_1, \ldots, n_k)$, a global minima $(a_1, a_2, \ldots, a_k)$ exists, where $a:=a_1 < a_2 < \cdots < a_k$ and $\sum a_j = \sum n_j$. Notice that
$$\forall i \ne j, n_i^3 + n_j^3 = (n_i+n_j)\left[(n_i+n_j)^2-3n_i n_j\right]\tag1$$
This means if the sum of $n_i$ and $n_j$ is fixed, we can make them closer to each other, as long as the order of all $n_l$'s is preserved, to decrease the sum of cubes.  We now prove the following properties of $\{ a_j: 1 \le j \le k\}$.
Property 1: $a_j-a_{j-1} \le 2, \forall 1<j\le k$. If not, we change $(a_{j-1}, a_j)$ to $(a_{j-1}+1, a_j-1)$ and the sum of cubes gets smaller, a contradiction.
Property 2: There can be no more than one $j$ such that $a_j-a_{j-1}=2$. If not, suppose $a_j-a_{j-1}=a_k-a_{k-1}=2, j < k$, then we can replace $(a_{j-1}, a_k)$ with $(a_{j-1}+1, a_k-1)$ and the sum of cubes will decrease, another contradiction.
With the above properties, we know  $a_i$'s are mostly consecutive with at most one gap where the difference is $2$.
Case 1: All $a_i$'s are consecutive. Then
$$
\sum_{i=0}^{k-1} (a+i)^3 - \left( \sum_{i=0}^{k-1} (a+i) \right)^2 =\sum_1^{a+k-1} j^3 - \sum_1^{a-1} j^3 - \left(\sum_1^{a+k-1} j - \sum_1^{a-1} j\right)^2 \\ 
= \left(\sum_1^{a+k-1} j\right)^2 - \left(\sum_1^{a-1} j \right)^2 - \left(\sum_1^{a+k-1} j - \sum_1^{a-1} j\right)^2 \\ 
=\left(\sum_1^{a+k-1} j - \sum_1^{a-1} j\right) \left[ \sum_1^{a+k-1} j + \sum_1^{a-1} j  - \left( \sum_1^{a+k-1} j - \sum_1^{a-1} j \right) \right]\\
=  \left( \sum_a^{a+k-1} j  \right) \left( 2 \sum_1^{a-1} j \right) \ge 0
$$
and $"=" \iff a=1$.
Case 2: One of the $a_j-a_{j-1}$ is $2$. Then $a_k=a+k$. In this case we can insert the number $x=a_{j-1}+1=a_j-1$ between $a_j$ and $a_{j-1}$ so that we have $k+1$ consecutive numbers, and we need to prove that
$$
f(x) := \sum_{i=0}^k (a+i)^3 - x^3 - \left[ \sum_{i=0}^k (a+i) - x \right]^2 \ge 0 \tag2
$$
where $x \in \{ a+1, a+2, \cdots, a+k-1 \}$. Let's expand the domain of $f$ to $[0,a+k]$. Notice the following:
(i) $f''(x) = -6x-2 <0, \forall x\ge0$;
(ii) $f(0)\ge 0$ from Case #1;
(iii) $f(a+k) \ge 0$, also from Case #1.
Therefore $(2)$ holds and we have strict inequality.$\blacksquare$
One last thing: What does this minima sequence look like? We give a simple example when $k=5$.

*

*If $\sum n_i$ is equal to sum of $5$ consecutive natural numbers, say $35$, then the minima is just $\{5,6,7,8,9\}$.


*If $\sum n_i$ is greater than $35$ but less than the next sum of $k=5$ consecutive numbers $(40=6+7+8+9+10)$,  assuming it's equal to $38$, then we just shift the last $38-35=3$ numbers of the sequence $\{5,6,7,8,9\}$ one size bigger to $\{5,6,8,9,10\}$.
A: We can go further to even state the biconditional equality condition. The following is a quote of Proposition 3 from Sum of Cubes is Square of Sum by Barbeau and Seraj, with permission from me, one of the authors:

We prove by induction that:
For integers $a_k$, if $1 \leq a_1 < a_2 < \cdots < a_n$ then
$$a_1^3 + a_2^3 + \cdots + a_n^3 \ge (a_1 + a_2 + \cdots + a_n)^2,$$
with equality if and only if $a_k = k$ for $1 \le k \leq n$.
This is clear for $n = 1$. Assume that the proposition holds for some natural $n$; we will prove it for $n+1$. Note that $a_k \ge k$ and that $a_{n+1} - k \ge a_{n+1-k}$ for all values of $k$. We begin with the fact that
$$(a_{n+1} - n)(a_{n+1} - n - 1) \ge 0$$
with equality if and only if $a_{n+1} = n+1$. Then expanding gives
\begin{align*}
 a_{n+1}^2 - a_{n+1} & \ge 2na_{n+1} - n(n+1) = 2 \left[ na_{n+1} - {{n(n+1)}\over 2} \right]\\
 & = 2 \left( \sum_{k=1}^n (a_{n+1} - k) \right) \ge 2 \sum_{k=1}^n a_{n+1-k} = 2 \sum_{k=1}^n a_k,
\end{align*}
with equality if and only if $a_k = k$ for all $k$. By the induction hypothesis, we have that
\begin{align*}
 \sum_{k=1}^{n+1} a_k^3 &=  a_{n+1}^3 + \sum_{k=1}^n a_k^3 \ge a_{n+1}^2 + 2a_{n+1}\left(\sum_{k=1}^n a_k \right) + \left(\sum_{k=1}^n a_k \right)^2\\
 & = \left(a_{n+1} + \sum_{k=1}^n a_k \right)^2 = \left( \sum_{k=1}^{n+1} a_k \right)^2,
\end{align*}
as desired.

