+0  
 
0
410
4
avatar

John computes the sum of the elements of each of the 21 two-element subsets of $\{1,2,3,4,5,6,7\}$. What is the sum of these 21 sums?

Guest Jan 17, 2015

Best Answer 

 #2
avatar+80866 
+10

Very nice, geno.....!!!

I'm not as crafty as geno, so I had to "brute-force" this one to see if I could discover another possible pattern....!!!

(1+2) + (1+3) + (1+4) + (1+5) + (1+6) + (1+7)

         +  (2+3) + (2+4) + (2+5) + (2+6) + (2+7)

                       + (3+4) + (3+5) + (3+6) + (3+7)

                                    + (4+5) + (4+6) + (4+7)

                                                 + (5+6) + (5+7)

                                                              + (6+7) 

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

(1+2)+(3+6)+(6+12)+(10+20)+(15+30)+(21+42) =

Notice that the sum of the first terms in the parentheses is just 56 = (8 x 7) = 1(8 x 7)

And notice that the sum of the second terms in the parentheses is just  112   = 2(8 x 7)

So we have 1(8 x 7)+ 2(8 x 7) = 3(8 x 7)= 8(7 x 3) = 8 x 21  =  (7+1)C(7,2) = (8)C(7,2)

Notice that the "pattern," is just (n+1)C(n,2)  ....where n = 7

BTW....this result can be extended to any two element subset sums of the first n positive integers.....for instance.....the sum of the two element subsets of the first 10 integers =(10+1)C(10,2)  = 11(45) = 495 ......

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

See the inductive proof of this below........

   

CPhill  Jan 17, 2015
Sort: 

4+0 Answers

 #1
avatar+17705 
+10

When creating these two elements subsets, you must use each of the elements 6 times (so each can be matched with each of the other 6 numbers).

So you need 6 1's, 6 2's, 6 3's, ..., 6 7's.

6[1 + 2 + 3 + 4 + 5 + 6 + 7]  =  6[28]  =  168

geno3141  Jan 17, 2015
 #2
avatar+80866 
+10
Best Answer

Very nice, geno.....!!!

I'm not as crafty as geno, so I had to "brute-force" this one to see if I could discover another possible pattern....!!!

(1+2) + (1+3) + (1+4) + (1+5) + (1+6) + (1+7)

         +  (2+3) + (2+4) + (2+5) + (2+6) + (2+7)

                       + (3+4) + (3+5) + (3+6) + (3+7)

                                    + (4+5) + (4+6) + (4+7)

                                                 + (5+6) + (5+7)

                                                              + (6+7) 

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

(1+2)+(3+6)+(6+12)+(10+20)+(15+30)+(21+42) =

Notice that the sum of the first terms in the parentheses is just 56 = (8 x 7) = 1(8 x 7)

And notice that the sum of the second terms in the parentheses is just  112   = 2(8 x 7)

So we have 1(8 x 7)+ 2(8 x 7) = 3(8 x 7)= 8(7 x 3) = 8 x 21  =  (7+1)C(7,2) = (8)C(7,2)

Notice that the "pattern," is just (n+1)C(n,2)  ....where n = 7

BTW....this result can be extended to any two element subset sums of the first n positive integers.....for instance.....the sum of the two element subsets of the first 10 integers =(10+1)C(10,2)  = 11(45) = 495 ......

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

See the inductive proof of this below........

   

CPhill  Jan 17, 2015
 #3
avatar+80866 
+5

Inductive proof that the total sum of all of the possible two element subset sums of the first n positive integers is given by .... (n + 1)C(n, 2)

Show that it is true for the first two positive integers

(2 + 1)C(2,2)  = 3(1) = 3

Asuume it's true for n = k....that is......

(k + 1)C(k, 2) = (k+1) [k!]/[ (k - 2)! 2!] = (k-1)(k)(k+1) / 2!

Prove it's true for n =  k + 1  ....that is...(k+1)C(k+1, 2) = (k)(k+1)(k+2) /2!

So we have

[(k + 1) + 1)] C(k+1, 2) =

(k + 1)C(k+1, 2)   + C(k+1, 2) =

(k + 1)[(k + 1)!] / [(k-1)!2!]  + [(k + 1)!] / [(k-1)!2!] =

(k + 1)[ (k+1)(k)] /2!  + [(k+1)(k) /2!] =

[(k + 1)(k) /2!] [ (k+1) + 1) ] =

[(k + 1)(k) /2!] [ (k+2) ] =

(k)(k+1)(k+2) / 2!   ......which is what we wished to show....

 

CPhill  Jan 19, 2015
 #4
avatar+18827 
+5

John computes the sum of the elements of each of the 21 two-element subsets of {1,2,3,4,5,6,7}.

What is the sum of these 21 sums ?

$$\small{\text{
$
sum = \frac{3}{2} * \left(\ 1*2+2*3+3*4+4*5+5*6+6*7\ \right) =
\frac{3}{2} * \left(\ 2+6+12+20+30+42\ \right)
$
}}$\\$
\small{\text{
$
= \frac{3}{2}*112=168
$
}}$\\\\$
\small{\text{
for n:
$
sum = \frac{3}{2} * \left(\ 1*2+2*3+3*4+4*5+5*6+6*7+\dots + (n-1)*n\ \right) = 3*\left( \begin{array}{c} n+1\\3 \end{array} \right)
$
}}$\\\\$
\small{\text{
$
= \dfrac{(n-1)n(n+1)}{2}
$
}}$\\\\$
\small{\text{
for n=7:
$
sum = 3*\left( \begin{array}{c} 8\\3 \end{array} \right)
=3*\frac{6*7*8}{2*3}=21*8=168
$
}}$$

heureka  Jan 20, 2015

10 Online Users

avatar
We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details