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
59.4k3535 gold badges247247 silver badges453453 bronze badges
asked May 2 "14 at 15:21
*

OwenOwen
14111 gold badge11 silver badge66 bronze badges
$endgroup$
12
| Show 7 more comments

7 Answers 7


Active Oldest Votes
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$
Add a comment |
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$.

For more information see Binomial coefficient and Arithmetic progression


Share
Cite
Follow
answered May 2 "14 at 15:28
*

BelgiBelgi
21.3k1414 gold badges7878 silver badges143143 bronze badges
$endgroup$
Add a comment |
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
80411 gold badge77 silver badges1111 bronze badges
$endgroup$
Add a phản hồi |
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
1,45799 silver badges2222 bronze badges
$endgroup$
Add a phản hồi |
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$.

Xem thêm: Tìm M Để Hàm Số Nghịch Biến Trên Khoảng Xác Định, Tìm M Để Hàm Số Đồng Biến Trên Khoảng Cho Trước


Share
Cite
Follow
edited May 2 "14 at 15:47
answered May 2 "14 at 15:41
Yves DaoustYves Daoust
201k1414 gold badges1201trăng tròn silver badges306306 bronze badges
$endgroup$
7
| Show 2 more comments
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
50.5k66 gold badges7171 silver badges215215 bronze badges
$endgroup$
Add a bình luận |
-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
36711 silver badge1111 bronze badges
$endgroup$
Add a comment |

Your Answer


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

Please be sure khổng lồ answer the question. Provide details & mô tả your research!

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.

To learn more, see our tips on writing great answers.


Draft saved
Draft discarded

Sign up or log in


Sign up using Google
Sign up using Facebook
Sign up using Thư điện tử and Password
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


Post Your Answer Discard

By clicking “Post Your Answer”, you agree to lớn our terms of service, privacy policy & cookie policy


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


The Overflow Blog
Featured on Meta
Linked
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
Subscribe lớn RSS
Question feed To subscribe khổng lồ this RSS feed, copy & paste this URL inkhổng lồ your RSS reader.


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
*

Your privacy

By clicking “Accept all cookies”, you agree Stachồng Exchange can store cookies on your device và discđại bại information in accordance with our Cookie Policy.