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.

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.
