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