# 1 + 2 + 3 + 4 + ⋯

190
I"m writing some software that takes a group of users & compares each user with every other user in the group. I need to display the amount of comparisons needed for a countdown type feature.

For example, this group <1,2,3,4,5> would be analysed like this:

1-2, 1-3, 1-4, 1-52-3, 2-4, 2-53-4, 3-54-5By creating little diagrams like this I"ve sầu figured out the pattern which is as follows:

Users - Comparisons2 - 13 - 3 (+2)4 - 6 (+3)5 - 10 (+4)6 - 15 (+5)7 - 21 (+6)8 - 28 (+7)9 - 36 (+8)I need khổng lồ be able to take any number of users, và calculate how many comparisons it will take to compare every user with every other user.

Bạn đang xem: 1 + 2 + 3 + 4 + ⋯

Can someone please tell me what the formula for this is?

combinatorics summation
Share
Cite
Follow
edited May 2 "14 at 15:23 MJD
asked May 2 "14 at 15:21 OwenOwen
\$endgroup\$
12

13
\$egingroup\$
The sum of \$0+cdots + n-1\$ is \$\$frac12(n-1)n.\$\$

Here \$n\$ is the number of users; there are 0 comparisons needed for the first user alone, 1 for the second user (to compare them lớn the first), 2 for the third user, and so on, up khổng lồ the \$n\$th user who must be compared with the \$n-1\$ previous users.

For example, for \$9\$ people you are adding up \$0+1+2+3+4+5+6+7+8\$, which is equal to lớn \$\$frac12cdot 8cdot 9= frac722 = 36\$\$ và for \$10\$ people you may compute \$\$frac12cdot9cdot10 = frac902 = 45.\$\$

Share
Cite
Follow
answered May 2 "14 at 15:25
community wiki
MJD
\$endgroup\$
15
\$egingroup\$
You want to lớn know how many ways there are lớn choose \$2\$ users froma mix of \$n\$ users.

Generally, the number of ways to lớn choose \$k\$ elements from a mix oforder \$n\$ (that is, all elements in the mix are distinct) is denotedby \$\$inomnk\$\$

và is equivalent to \$\$fracn!(n-k)!k!\$\$

In the case of \$k=2\$ the latter equals khổng lồ \$\$fracn!(n-2)!2!=fracn(n-1)2\$\$

which is also the sum of \$1+2+...+n-1\$.

Share
Cite
Follow
answered May 2 "14 at 15:28 BelgiBelgi
\$endgroup\$
5
\$egingroup\$
The following way to getting the solution is beautiful and said to have been found by young Gauss in school. The idea is that the order of adding \$1+2+cdots+n=S_n\$ does not change the value of the sum. Therefore:

\$\$1 + 2 + ldots + (n-1) + n=S_n\$\$\$\$n + (n-1) + ldots + 2 + 1=S_n\$\$

Adding the two equations term by term gives

\$\$(n+1)+(n+1)+ldots+(n+1)=2S_n\$\$

so \$n(n+1)=2S_n\$. For \$n\$ persons, there are \$S_n-1\$ possibilities, as others answers have sầu shown already nicely.

Share
Cite
Follow
answered May 2 "14 at 15:33 binkyhorsebinkyhorse
\$endgroup\$
0
\$egingroup\$
The discrete sum up to a finite value \$N\$ is given by,

\$\$sum_n=1^N n = frac12N(N+1)\$\$

Proof:

The proof by induction roughly boils down to:

\$\$S_N = 1+ 2 +dots+N\$\$

\$\$S_N+1= 1+ 2 + dots + N + (N+1) = underbracefrac12N(N+1)_S_N + (N+1)\$\$

assuming that the induction hypothesis is true. The right hvà side:

\$\$fracN(N+1)2+(N+1)=frac(N+1)(N+2)2\$\$

which is precisely the induction hypothesis applied to \$S_N+1\$.

Just for your own curiosity, the case \$N=infty\$ is of course divergent. However, with the use of the zeta function, it may be regularized lớn yield,

\$\$sum_n=1^inftyn = zeta(-1)=-frac112\$\$

Share
Cite
Follow
answered May 2 "14 at 15:31 JPhyJPhy
\$endgroup\$
0
\$egingroup\$
\$\$N=2: 1 + 2 = (1 + 2) = 1 imes3\$\$

\$\$N=4: 1 + 2 + 3 + 4 = (1 + 4) + (2 + 3) = 2 imes5\$\$

\$\$N=6: 1 + 2 + 3 + 4 + 5 + 6 = (1 + 6) + (2 + 5) + (3 + 4) = 3 imes7\$\$

\$\$N=8: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8= (1 + 8) + (2 + 7) + (3 + 6)+ (4 + 5) = 4 imes9\$\$

More generally, \$N/2 imes(N + 1)\$.

For odd \$N\$, sum the \$N-1\$ first terms (using the even formula) together with \$N\$, giving \$(N-1)/2 imes N+N=N imes(N+1)/2\$.

Share
Cite
Follow
edited May 2 "14 at 15:47
answered May 2 "14 at 15:41
Yves DaoustYves Daoust
\$endgroup\$
7
0
\$egingroup\$
Here is another way lớn find the sum of the first \$n\$ squares that generalizes to sums of higher powers.

\$(k+1)^2 - k^2 = 2k+1\$

\$sum_k=1^n ( (k+1)^2 - k^2 ) = sum_k=1^n (2k+1)\$

\$(n+1)^2 - 1^2 = 2 sum_k=1^n k + n\$

\$sum_k=1^n k = frac (n+1)^2 - 1 - n 2 = fracn^2+n2\$

Share
Cite
Follow
answered May 3 "14 at 7:11
user21820user218trăng tròn
\$endgroup\$
-1
\$egingroup\$
This is kind of a pseubởi vì code:

Say you have sầu n number of people, và you labeled them.

for i in (1,2,3,...,n), person i need lớn compare with all the people who has a number larger (strictly), so person i need to compare (n-i) times.

so adding up would be(n-1) + (n-2) + ... + 3 + 2 + 1...

which would be the sum from 1 to lớn (n-1)

Share
Cite
Follow
answered May 2 "14 at 15:26
TYZTYZ
\$endgroup\$

Thanks for contributing an answer lớn hibs.vnematics Staông chồng Exchange!

But avoid

Asking for help, clarification, or responding lớn other answers.Making statements based on opinion; back them up with references or personal experience.

Use hibs.vnJax to format equations. hibs.vnJax reference.

Draft saved

Submit

### Post as a guest

Name
E-Mail Required, but never shown

### Post as a guest

Name
Thư điện tử

Required, but never shown

## Not the answer you're looking for? Browse other questions tagged combinatorics summation or ask your own question.

The Overflow Blog
Featured on Meta
122
Proof \$1+2+3+4+cdots+n = fracn imes(n+1)2\$
83
What is the term for a factorial type operation, but with summation instead of products?
8
Formula for the number of connections needed lớn connect every node in a set?
Related
2
Scheduling a team based activity with 10 different teams & X different games. Every team must meet each other ONCE but never twice,
1
Finding the minimum wins in a round-robin tournament.
1
Formulating an equation for a group sorting program.
0
Number of distinguishable permutations with repetition and restrictions
1
Understanding a Proof in COMBINATORICA 3 ( 3 - 4 ) (1983) 325--329
2
Finding statistical data for repeated surveys in a population
0
In how many ways can 'i' Indian, 'j' chinese, 'k' mexicans, 'l' americans and 'm' canadians be arranged in groups?
0
The probability that any of the teams certainly win. The number of encounters which make this probability 98%.
3
The hibs.vn of password policy anti-patterns
Hot Network Questions more hot questions

Question feed

hibs.vnematics
Company
Staông xã Exchange Network
site design / hình ảnh sản phẩm © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev2021.6.3.39424

hibs.vnematics Stachồng Exchange works best with JavaScript enabled 