**Problem**: Find a closed form for the sum

$ \displaystyle \sum_{i=1}^n \sum_{j=i+1}^n i \cdot j = 1 \cdot 2+1 \cdot 3+\cdots+1 \cdot n+2 \cdot 3+2 \cdot 4+\cdots+2 \cdot n+\cdots+(n-1) \cdot n $.

**Solution**: Consider the expansion of

$ \displaystyle (1+2+\cdots+n)^2 = \sum_{i=1}^n \sum_{j=1}^n i \cdot j $.

It's not hard to see that if we let the desired sum be $ S $, we have

$ (1+2+\cdots+n)^2 = 2S+(1^2+2^2+\cdots+n^2) $

since each pair is counted twice and the squared terms are there. But we can simplify the sums by well-known formulas to get

$ \frac{n^2(n+1)^2}{4} = 2S+\frac{n(n+1)(2n+1)}{6} $,

which becomes

$ S = \frac{n(n-1)(n+1)(3n+2)}{24} $

after massive simplification. QED.

--------------------

Comment: Symmetry was definitely the best way to approach this problem (or as far as I know anyway). You could've found a lot of ugly summations to get to the desired expression as well.

--------------------

Practice Problem: Can you generalize? In any way, shape, or form.

Have fun in boston ^^ *make deep connections so christie says...*

ReplyDeletemna851 generalized in this thread on AoPS

ReplyDeleteWell there are other generalizations, too. For instance, the sum of the products taking 3 terms at a time.

ReplyDeleteHmm how do you do it three at a time?

ReplyDeleteI would take (1+2+...+n)^3 - 3*(1^2+2^2+...+n^2)(1+2+...+n) + 2(1^3+2^3+...+n^3) and divide by 6... it's sorta ugly. With a program you could expand f(x) = (x-1)(x-2)...(x-n) and find the coefficient of x^{n-3}.

ReplyDeletefine just ignore me -___- *i know i'm spamming*

ReplyDeleteNo I wasn't ignoring you... hope you're having fun in HK, too.

ReplyDelete