help with mathematical induction exercise the instructions say: "Consider n and $a_1<a_2<...<a_n$ natural numbers, $n\ge1$. Prove that $$(\sum_{k=1}^n a_k)^2 \le \sum_{k=1}^n a_k^3$$"
this is how I proceeded:
induction base: n = 1 $\implies a_1^2 \le a_1^3$ which is always true, since $a_1$ is a natural number
inductive hypothesis: I assume $(\sum_{k=1}^n a_k)^2 \le \sum_{k=1}^n a_k^3$ is true for $n\in\mathbb N$
inductive step: I verify that $(\sum_{k=1}^{n+1} a_k)^2 \le \sum_{k=1}^{n+1} a_k^3$
$(\sum_{k=1}^n a_k + a_{n+1})^2 \le \sum_{k=1}^{n} a_k^3+a_{n+1}^{3}$
$(\sum_{k=1}^n a_k)^2 + a_{n+1}^2 +2a_{n+1}\sum_{k=1}^n a_k \le \sum_{k=1}^{n} a_k^3+a_{n+1}^3$
$(\sum_{k=1}^n a_k)^2 \le \sum_{k=1}^n a_k^3$ is the inductive hypothesis, therefore I only have to verify that $a_{n+1}^2 +2a_{n+1}\sum_{k=1}^n a_k \le a_{n+1}^3$.
This is where I'm having trouble. anyways, I rewrote the this equation this way:
$2\sum_{k=1}^n a_k \le a_{n+1}^2-a_{n+1}$
since both quantities on the sides of the inequality are positive numbers, I can raise them to the square:
$(\sum_{k=1}^n a_k)^2 \le \frac{a_{n+1}^4-2a_{n+1}^3 + a_{n+1}^2}{4}$
$(\sum_{k=1}^n a_k)^2 \le \frac{a_{n+1}^2(a_{n+1}^2 -2a_{n+1}+1}{4}$
$(\sum_{k=1}^n a_k)^2 \le \frac{a_{n+1}^2(a_{n+1} -1)^2}{4}$
I think I have to somehow prove that
$\frac{a_{n+1}^2(a_{n+1} -1)^2}{4} \ge \sum_{k=1}^n a_k^3$
but I don't know how. thank you for the help :)
 A: As you pointed out, you need to prove that $2\sum_{k=1}^n a_k \leq a_{n+1}^2-a_{n+1}$. And you have the hypothesis $a_1<\dots<a_{n+1}$.
Then we have that:
$2\sum_{k=1}^n a_k\leq 2\sum_{k=1}^n (a_{n+1}-k) = 2na_{n+1}-(n+1)n$, since $a_{n+1-k} \leq a_{n+1}-k$.
So, it suffices to prove that $2na_{n+1}-(n+1)n\leq a_{n+1}^2-a_{n+1}$, that is:
$(2n-a_{n+1}+1)a_{n+1}\leq (n+1)n$, and because of our hypothesis, we know that $a_{n+1}\geq n$. If $a_{n+1} = n$, there is nothing to be done, and if $a_{n+1}>n$, then there is $c>0$ such that $a_{n+1} = n+c$. In this case we have:
$(2n-a_{n+1}+1)a_{n+1} = (2n-n-c+1)(n+c) = (n+1-c)(n+c) =$
$= (n+1)(n+c) - c(n+c) = (n+1)n + c(n+1-(n+c)) =$
$(n+1)n + c(1-c) \leq (n+1)n$, as we wanted to show.
A: As you pointed out, it suffices to prove for natural numbers $a_1, \dots, a_n$: $2\sum_{k=1}^na_k\leq a_{n+1}^2-a_{n+1}$, given that $a_i<a_j$ if $i<j$. To prove this, proceed by induction.
The base case is for $n=1$, which converts to $2a_1\leq a_2^2-a_2$. Now we exploit the fact that $a_2\geq a_1 +1$:
$$a_2^2-a_2 \geq (a_1+1)^2-a_1-1=a_1^2+a_1\geq 2a_1$$
Now for the inductive step, we assume that the hypothesis holds up to some number $n$, and we prove the $n+1$. To prove this we write as follows:
$$2\sum_{k=1}^{n+1}a_k\leq 2a_{n+1}+\sum_{k=1}^na_k\leq 2a_{n+1}+a_{n+1}^2-a_{n+1}=a_{n+1}^2+a_{n+1}$$
We wish to prove the $a_{n+1}^2+a_{n+1}$ to be smaller than or equal to $a_{n+2}^2-a_{n+2}$. This is apparent once we factor:
$$a_{n+2}(a_{n+2}-1)\geq (a_{n+1}+1)a_{n+1}$$
Using $a_{n+2}\geq a_{n+1} +1$
