Summation of Combinations

If we take the hint for those pairs from $1$ to $4$ ,

The total sum of possible pairs could be enumerated, that is,

$1 \times 2$

$1 \times 3$

$1 \times 4$

$2 \times 3$

$2 \times 4$

$3 \times 4$

We could simplify this to

$1 \times ( 2 + 3 + 4)$

$2 \times (3+ 4)$

$3 \times 4$ .

In a similar way, if we have 10 numbers to choose from, we can simplify the sum to be

$1 \times ( 2 + 3 + ... + 10)$

$2 \times (3+ 4 + ... + 10)$

$3 \times (4 + 5 + ...+ 10)$

...

$8 \times (9+10)$

$9 \times 10$ .

Thus, for an integer $n$ , the possible combinations would be

$\large \sum_{k=1}^{n-1}(k \sum_{j=k+1}^{n} j)$

$\large \sum_{k=1}^{n-1}k (\frac{n-k}{2}(n+k+1))$

$\large \sum_{k=1}^{n-1}k (\frac{n^{2}-k^{2}+n-k}{2})$

$\large \sum_{k=1}^{n-1} (\frac{n^{2}k-k^{3}+nk-k}{2})$

$\large \frac {1}{2} \sum_{k=1}^{n-1} (k(n^{2}+n)-k^{2}-k^{3})$

Using the formula for summation of consecutive integers, squares, and cubes, we simplify this to

$\large \frac {1}{2} (\frac{(n^2+n)(n^2-n)}{2}-\frac{(n-1)(n)(2n-1)}{6}-\frac{(n-1)^{2}(n)^{2}}{4})$

Now, substituting $n=100$ , we get $\large \boxed {12582075}.$

We want the sum of the bold products, which lie under the diagonal.

Let's sum everything, subtract the sum of the diagonal and divide by 2.

The whole sum is $(1+2+\cdots+100)·(1+2+\cdots+100)=5050^2$ .

The sum of the diagonal is $1^2+2^2+\cdots+100^2=338'350$ .

Answer is then $\dfrac{\Big(\sum^{100}_{i=1}i\Big)^2-\sum^{100}_{i=1}i^2}{2}=\dfrac{5050^2-338'350}{2}=\boxed{12'582'075}$ .

---

I used the well known formulas:

$\sum^n_{i=1}i\,=\,\dfrac{n(n+1)}{2}$ and $\sum^n_{i=1}i^2\,=\,\dfrac{n(n+1)(2n+1)}{6}$

First, we establish the set of integers from 1 to 100:

$A=\left\{ n|n\in { Z }\wedge 1\le n\le 100 \right\} =\{ 1,2,3,4,5,6,...,98,99,100\}$

Then, we find the unique combinations by going down the set.

Starting off with $1$ , we go down the set finding $\left( 1,2 \right)$ , $\left( 1,3 \right)$ , $\left( 1,4 \right)$ , $\left( 1,5 \right)$ , and so on.

There are 99 of these combinations based on $1$ , as $\left( 1,1 \right)$ is rejected.

The two numbers in each combination above are multiplied together and all the 99 products are added to give:

$1(2)+1(3)+1(4)+...+1(99)+1(100)\\ =1(2+3+4+...+99+100)\\ =1\left[ (1+2+3+4+...+99+100)-(1) \right] \\ =1(\frac { 100\times 101 }{ 2 } -\frac { 1\times 2 }{ 2 } )\\ =1(5050-\frac { 1\times 2 }{ 2 } )$

Then we move on to $2$ , finding $\left( 2,3 \right)$ , $\left( 2,4 \right)$ , $\left( 2,5 \right)$ , $\left( 2,6 \right)$ , and so on, as we move down the set.

There 98 such combinations based on $2$ , because $\left( 2,1 \right)$ is already counted for as $\left( 1,2 \right)$ , and $\left( 2,2 \right)$ is rejected.

Similarly, the two numbers in each combination above are multiplied together and all the 98 products are added to give:

$2(3)+2(4)+2(5)+...+2(99)+2(100)\\ =2(3+4+5+...+99+100)\\ =2[(1+2+3+4+...+99+100)-(1+2)]\\ =2(\frac { 100\times 101 }{ 2 } -\frac { 2\times 3 }{ 2 } )\\ =2(5050-\frac { 2\times 3 }{ 2 } )$

There are 99 such "sums of products" as there are "sums of products" based on $1$ through $99$ , but there is no "sum of products" based on $100$ .

We can now generalise the "sum of products" for any element n in the set A:

$n\left[ 5050-\frac { n\left( n+1 \right) }{ 2 } \right] \\ =n\left[ 5050-\frac { { n }^{ 2 }+n }{ 2 } \right] \\ =n\left[ -\frac { { n }^{ 2 }+n-10100 }{ 2 } \right] \\ =-\frac { { n }^{ 3 }+{ n }^{ 2 }-10100n }{ 2 }$

Finally, we find the sum of all 99 "sums of products":

$\sum _{ n=1 }^{ 99 }{ -\frac { { n }^{ 3 }+{ n }^{ 2 }-10100n }{ 2 } } =\boxed { 12582075 }$