Tuesday, June 20, 2006

All Paired Up. Topic: Algebra/NT. Level: AIME.

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.


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

  2. mna851 generalized in this thread on AoPS

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

  4. Hmm how do you do it three at a time?

  5. I 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}.

  6. fine just ignore me -___- *i know i'm spamming*

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