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