1 + 2 + 3 + 4 + ⋯

     
I"m writing some software that takes a group of users và compares each user with every other user in the group. I need lớn 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 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 to lớn be able lớn take any number of users, và calculate how many comparisons it will take to lớn 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?


giới thiệu
Cite
Follow
edited May 2, 2014 at 15:23
*

MJD
63.1k3737 gold badges280280 silver badges500500 bronze badges
asked May 2, 2014 at 15:21
*

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

7 Answers 7


Sorted by: Reset to default
Highest score (default) Date modified (newest first) Date created (oldest first)
16
$egingroup$
You want to lớn know how many ways there are to choose $2$ users froma mix of $n$ users.

Generally, the number of ways lớn choose $k$ elements from a phối oforder $n$ (that is, all elements in the set are distinct) is denotedby $$inomnk$$

and is equivalent to $$fracn!(n-k)!k!$$

In the case of $k=2$ the latter equals lớn $$fracn!(n-2)!2!=fracn(n-1)2$$

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

For more information see Binomial coefficient & Arithmetic progression


mô tả
Cite
Follow
answered May 2, 2014 at 15:28
*

BelgiBelgi
22.4k1616 gold badges9090 silver badges150150 bronze badges
$endgroup$
địa chỉ cửa hàng a comment |
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 to lớn the first), 2 for the third user, and so on, up to 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$$ & for $10$ people you may compute $$frac12cdot9cdot10 = frac902 = 45.$$


chia sẻ
Cite
Follow
answered May 2, năm trước at 15:25
community wiki
MJD
$endgroup$
add a phản hồi |
5
$egingroup$
The following way to lớn getting the solution is beautiful and said lớn 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 shown already nicely.


chia sẻ
Cite
Follow
answered May 2, năm trước at 15:33
*

binkyhorsebinkyhorse
80411 gold badge77 silver badges1111 bronze badges
$endgroup$
showroom a comment |
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 hand side:

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

which is precisely the induction hypothesis applied khổng lồ $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$$


mô tả
Cite
Follow
answered May 2, 2014 at 15:31
*

JPhyJPhy
1,6561010 silver badges2222 bronze badges
$endgroup$
địa chỉ cửa hàng a comment |
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)$.

Xem thêm: Tổng Hợp Các Đoạn Văn Tiếng Anh Viết Về Sở Thích Sưu Tập Tem Bằng Tiếng Anh

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


giới thiệu
Cite
Follow
edited May 2, năm trước at 15:47
answered May 2, 2014 at 15:41
user65203user65203
$endgroup$
7
$egingroup$
corsiKa: the formula explicitly shows the sum from 1 khổng lồ $N$ inclusive (triangular numbers) & is perfectly correct. It is NOT the formula for the number of comparisons between $N$ users. $endgroup$
–user65203
May 2, 2014 at 21:38


$egingroup$ The sum must be taken from $1$ lớn $Users-1$ inclusive. $endgroup$
–user65203
May 2, 2014 at 21:51
| Show 2 more comments
0
$egingroup$
Here is another way to 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$


mô tả
Cite
Follow
answered May 3, 2014 at 7:11
user21820user21820
54.7k88 gold badges9090 silver badges236236 bronze badges
$endgroup$
add a comment |
-1
$egingroup$
This is kind of a pseudo code:

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

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

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

Xem thêm: Nước Ta Hòa Mạng Internet Vào Năm Nào ? Internet Tại Việt Nam

which would be the sum from 1 khổng lồ (n-1)


mô tả
Cite
Follow
answered May 2, 2014 at 15:26
TYZTYZ
36711 silver badge1313 bronze badges
$endgroup$
add a phản hồi |

You must log in khổng lồ answer this question.


Not the answer you're looking for? Browse other questions tagged .
Featured on Meta
Linked
132
Proof $1+2+3+4+cdots+n = fracn imes(n+1)2$
98
What is the term for a factorial type operation, but with summation instead of products?
8
Formula for the number of connections needed to lớn connect every node in a set?
Related
2
Scheduling a team based activity with 10 different teams và 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 & 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 và 'm' canadians be arranged in groups?
2
The giaynamdavinci.com of password policy anti-patterns
0
Trying lớn understand multisets. Given 4 random letters, what is the formula for finding the number of ways khổng lồ get multisets? Then for 5 letters?
3
Efficient way lớn rotate through partitions with subsets of kích cỡ three
Hot Network Questions more hot questions

Question feed
Subscribe to RSS
Question feed to lớn subscribe lớn this RSS feed, copy and paste this URL into your RSS reader.


giaynamdavinci.comematics
Company
Stack Exchange Network
Site thiết kế / biểu tượng logo © 2022 Stack Exchange Inc; user contributions licensed under CC BY-SA. Rev2022.12.21.43127


Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device & disclose information in accordance with our Cookie Policy.