Induction on $S(n,k)$ Consider $$S(n,k):= 1^{k}+\ldots+n^{k}.$$
I have to find a formula for $$S(n,3).$$
After trying for some n values I found out that
$$S(1,3)=1^{3}=1^{2}$$
$$S(2,3)=1^{2} +2^{2}=3^{2}$$
$$S(3,3)=1^{2} +2^{2}  +3^{3}=6^{2}$$
$$S(4,3)=1^{2} +2^{2} +3^{3}+4^{3}=10^{2}$$
$$S(5,3)=1^{2} +2^{2} +3^{3}+4^{3}+5^{3}=15^{2}$$
Which led to the conjecture that $$S(n,3)=\left(1+\ldots+n\right)^{2}$$
I know for a fact that $$S(n,1)=\frac{n^{2}}{2}+\frac{n}{2}$$
Therefore,
$$S(n,3)=\left(\frac{n^{2}}{2}+\frac{n}{2}\right)^2$$
But when trying to prove the formula using induction I get stuck on the inductive step.
$$S(k+1,3)=1^{3}+\ldots+k^{3}+(k+1)^3=\left(\frac{(k+1)^{2}}{2}+\frac{k+1}{2}\right)^2$$
I don't know how to proceed. I have tried manipulating the RHS, but it's been fruitless.
 A: Assuming that $S(k,3)=(\frac{k^2}{2}+\frac{k}{2})^2$ from the induction step, $$S(k+1,3)=1^3+\dots k^3 +(k+1)^3 = S(k,3)+(k+1)^3 = \frac{k^4+2k^3+k^2}{4}+(k+1)^3=\frac{k^4+2k^3+k^2+4k^3+12k^2+12k+4}{4}=\frac{k^4+6k^3+13k^2+12k+4}{4}=\frac{(k^4+k^3)+(5k^3+5k^2)+(8k^2+8k)+(4k+4)}{4}=\frac{(k+1)(k^3+5k^2+8k+4)}{4}=\frac{(k+1)((k^3+k^2)+(4k^2+4k)+(4k+4))}{4}=\frac{(k+1)^2(k^2+4k+4)}{4}=\frac{((k+1)(k+2))^2}{4}=(\frac{(k+1)^2+(k+1)}{2})^2$$ which is what we were looking for.
A: On inductive step we can use
$$1^3+2^3+\cdots +k^3+(k+1)^3 = (1+2+\cdots +k)^2 +(k+1)^3 =(1+2+\cdots +k+(k+1))^2$$
Last equality is same with
$$\left( \frac{k(k+1)}{2} \right)^2 +(k+1)^3 = \left( \frac{(2+k)(k+1)}{2} \right)^2$$
and can be easy checked.
A: NOT an answer.
Induction is okay to prove this identity, but my favorite proof is the following one:
Observe that $4n = (n+1)^2 - (n-1)^2.$ This implies $ 4n^3 = (n+1)^2n^2 - n^2(n-1)^2.$ The right side is telescopic, and so $ \Sigma_ {i=1}^{n} 4n^3 =  (n+1)^2n^2.$ This completes the proof.
