7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ There are many. Graham, Knuth, & Patashnik, Concrete Mathematics, Section $2.5$, give six and mention two more that will be covered in later sections. $\endgroup$ May 10 '13 at 15:23
  • $\begingroup$ Given that you can't define the sum without induction, it's pretty hard to prove it without induction. You can give visual arguments or use results that were in turn proven by induction, however. $\endgroup$ May 10 '13 at 15:25
9
$\begingroup$

$$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):

Sum of squares

Sum of Squares(2)

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.

$\endgroup$
1
  • 3
    $\begingroup$ Telescoping summation is just a form of induction, of course. $\endgroup$ May 10 '13 at 15:26
3
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ Better yet: Show that if $x^{\overline{m}} = x (x + 1) \ldots (x + m - 1)$ (rising factorial power), then $\Delta k^{\overline{m}} = m k^{\overline{m - 1}}$. Sum up over $0 \le k \le n$. Any polynomial can be expressed in terms of rising factorial powers (in particular $x^2$), and you are set. $\endgroup$
    – vonbrand
    May 10 '13 at 16:42
2
$\begingroup$

$\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}$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.