In another post I made, an answer pointed me toward Faulhabers formula for sum of k-th powers of the n first integers.
The answer I got of how to reach a formula for $P(n)=\sum_{k=0}^{n}k^2$ looks something like this:
If $P(n)$ is a polynomial function of degree $k+1$, then $S(n)=P(n)-P(n-1)$ is a polynomial function of degree $k$. $$P(n)=an^3+bn^2+cn+d$$ $$S(n)=a(n^3-(n-1)^3)+b(n^2-(n-1)^2)+c(n-(n-1))$$ where the $n^3$-term is cancelled out.
If $P(n)=\sum_{k=0}^{n}k^2$, then $S(n)=P(n)-P(n-1)$ is the last element in the sum, $n^2$
Therefor $n^2=a(n^3-(n-1)^3)+b(n^2-(n-1)^2)+c(n-(n-1))$
You can solve this equation system and get the formula.
My only question is why we can make the assumption that the formula will be a polynomial, with the last integer as a variable, in the first place?
As far as I know it is just an assumption; that is, this is a proof that if $\sum_{k=0}^nk^2$ is a polynomial in terms of $n$, then it is $n(n+1)(2n+1)/6$. That this formula is actually correct can then be proved through induction.
I prefer a slightly different approach to this, which I think is a little more intuitive if you’re familiar with binomial coefficients. We will use the identity $\sum_{m=k}^n\binom{m}{k}=\binom{n+1}{k+1}$ (this is easy to prove with induction and the formula for binomial coefficients).
\begin{align} 2\binom{n}{2} &= n^2-n \\ 2\sum_{k=2}^n\binom{k}{2} &= 2\binom{n+1}{3} \\ &= \sum_{k=2}^nk^2-\sum_{k=2}^nk \\ &= \sum_{k=1}^nk^2-\sum_{k=1}^nk && 1^2=1 \\ &= \sum_{k=1}^nk^2-\binom{n+1}{2} && k=\binom{k}{1} \\ \sum_{k=1}^nk^2 &= 2\binom{n+1}{3}+ \binom{n+1}{2} \end{align}
The same method can be used for any power, and using the formula for binomial coefficients shows that this is identical to the polynomial form.