Proving $\sum_{k=1}^n{k^2}=\frac{n(n+1)(2n+1)}{6}$ without induction

Question

I was looking at: $$\sum_{k=1}^n{k^2}=\frac{n(n+1)(2n+1)}{6}$$

It's pretty easy proving the above using induction, but I was wondering what is the actual way of getting this equation?

Answer 1

$$n^{3}-(n-1)^{3}=3n^{2}+3n+1$$ $$(n-1)^{3}-(n-2)^{3}=3(n-1)^{2}+3(n-1)+1$$ $$\vdots$$ $$2^{3}-1^{3}=3(1)^{2}+3(1)+1$$

Now use telescopic cancellation.

Here are some "proof without words"(I find them more elegant):

Finally a more generalized form:$$1^{k}+2^{k}+\cdots+n^{k}=\sum\limits_{i=1}^{k}S(k,i)\binom{n+1}{i+1}i!$$ Where S(k,i) represents the Stirling number of the second kind.

Answer 2

HINT:

To find $\sum_{1\le r\le n}r^m$ we can utilize the identity

$$(r+1)^{m+1}-r^{m+1}$$ $$=\sum_{1\le t\le m+1}\binom {m+1}t r^{m+1-t}=(m+1)r^m+\sum_{2\le t\le m+1}\binom {m+1}t r^{m+1-t}$$ and need to know $\sum_{1\le r\le n}r^s$ for $0\le s\le m-1$

For $m=2,$ $$(r+1)^3-r^3=3r^2+\sum_{2\le t\le 3}\binom 3t r^{3-t}=3r^2+3r+1$$

Put $r=1,2,3,\cdots,n-1,n$ and add to get $$(n+1)^3-1^3=3\sum_{1\le r\le n}r^2+3\sum_{1\le r\le n}r+\sum_{1\le r\le n}1$$

Now, we know $\sum_{1\le r\le n}r=\frac{n(n+1)}2$ and $\sum_{1\le r\le n}1=n$

Answer 3

Define $\Delta S(n) = S(n + 1) - S(n)$. Show that $\Delta$ is a homomorphism from polynomials of degree $\le k+1$ to polynomials of degree $\le k$. Find $\Delta n^k, 0 \le k\le 3$. Find a preimage of $n^2$.

Answer 4

Start with: $$ \sum_{0 \le k \le n} z^k = \frac{1 - z^{n + 1}}{1 - z} $$ Note that: $$ z \frac{d}{dz} \sum_{0 \le k \le n} a_k z^k = \sum_{0 \le k \le n} k a_k z^k $$ Differentiate twice, evaluate for $z = 1$ (applying l'Hôpital generously). This works for any power.

Answer 5

$\displaystyle\sum_{k=0}^{n} k^{3} + (n+1)^{3} = 0^{3} + \sum_{k=1}^{n+1}k^{3} = \sum_{k=0}^{n} (k+1)^{3} = \sum_{k=0}^{n} (k^{3} +3k^{2}+3k+1)$

$\displaystyle = \sum_{k=0}^{n} k^{3} + \sum_{k=0}^{n} k^{2} + 3 \frac{n(n+1)}{2} + (n+1)$

$ \displaystyle \implies 3 \sum_{k=0}^{n} k^{2} = 3 \sum_{k=1}^{n} k^{2} = (n+1)^{3} -3 \frac{n(n+1)}{2} -(n+1) = \frac{n(n+1)(2n+1)}{2}$

Similarly, the sum $\displaystyle \sum_{k=1}^{n} k^{3} $ can be evaluated by starting with the equation $\displaystyle\sum_{k=0}^{n} k^{4} + (n+1)^{4}= 0^{4} + \sum_{k=1}^{n+1} k^{4}$