9
$\begingroup$

It's straightforward to show that

$$\sum_{i=1}^ni=\frac{n(n+1)}{2}={n+1\choose2}$$

but intuitively, this is hard to grasp. Should I understand this to be coincidence? Why does the sum of the first $n$ natural numbers count the number of ways I can choose a pair out of $n+1$ objects? What's the intuition behind this?

$\endgroup$
  • $\begingroup$ I actually had similar encounter even with sum of an A.P Try it. It has $^{n}C_1$ and $^{n}C_2$ ! $\endgroup$ – Mann May 8 '15 at 16:17
  • $\begingroup$ What's an "A.P"? I'm sorry, I'm only a student. $\endgroup$ – user238435 May 8 '15 at 16:18
  • $\begingroup$ Arithmetic Progression. $\endgroup$ – user223391 May 8 '15 at 16:19
  • 1
    $\begingroup$ @leonbloy I'm not asking for a proof though, I was looking for intuition. $\endgroup$ – user238435 May 8 '15 at 16:30
  • 1
    $\begingroup$ @user238435 The answers include intuition-based proofs. Also see my last image in math.stackexchange.com/questions/44759/… $\endgroup$ – leonbloy May 8 '15 at 16:31
5
$\begingroup$

Consider a tournament with $n+1$ teams each playing each other. We will count the number of matches played in two ways.

  • Every match is played between two teams. This inturn implies that the number of matches is $\dbinom{n+1}2$.
  • We will now count the number of distinct matches played team by team.
    • The number of matches played by the first team is $n$.
    • The number of matches played by the second team is $n-1$, since their match with the first team has already been accounted for.
    • The number of matches played by the third team is $n-2$, since their matches with the first and second team have already been accounted for.
    • The number of matches played by the $k^{th}$ team is $n-k+1$, since their matches with the first $k-1$ teams have already been accounted for. Hence, the total number of matches is $$n+(n-1) + (n-2) + \cdots + 1$$
$\endgroup$
  • 1
    $\begingroup$ While all the answers have been helpful, this one was pedagogically best for my grasping the intuition. Very clear explanation. $\endgroup$ – user238435 May 8 '15 at 16:37
4
$\begingroup$

Suppose that you want to choose a subset $\{m,n\}$ with two elements of the set $$ \{1,2,\dotsc,n+1\} $$ Count this in two ways one of them naturally equals $\binom {n+1}2$ and for the other observe that

If $max\{m,n\}=2$ then we have one subsets $\{m,n\}$.
If $max\{m,n\}=3$ then we have two subsets $\{m,n\}$.
$\vdots$
If $max\{m,n\}=n+1$ then we have $n$ subsets $\{m,n\}$.

Now add up these cases to derive the identity.$\square$

$\endgroup$
3
$\begingroup$

This is the classic proof without words, from https://maybemath.wordpress.com/

enter image description here

That doesn't help with this part of your question:

Why does the sum of the first $n$ natural numbers count the number of ways I can choose a pair out of $n+1$ objects?

Here's a way to rephrase @user17762 's excellent accepted answer.

Imagine $n+1$ kids in a room. Each shakes hands with all the others. Then each kid shakes hands $n$ times, so there are $n(n+1)$ handshakes - each counted twice. You can pick a pair of kids (that is, a handshake) in $n(n+1)/2$ ways. But you can also think about the kids shaking hands as they enter the room one at a time. The second kid coming has one hand to shake. The third has two, and so on, for a total of $1 + 2 + \cdots + n$.

$\endgroup$
2
$\begingroup$

The intuition is that for the pairs can be listed in the following way.

$$\begin{array}{ccccccc} 1,2 & & & & & & \\ 1,3 & 2,3 & & & & & \\ 1,4 & 2,4 & 3,4 & & & & \\ 1,5 & 2,5 & 3,5 & 4,5 & & & \\ 1,6 & 2,6 & 3,6 & 4,6 & 5,6 & & \\ 1,\vdots & 2,\vdots & 3,\vdots & 4,\vdots & 5,\vdots &\ddots & \\ 1,n+1 & 2,n+1 & 3,n+1 & 4,n+1 & 5,n+1 & \cdots & n,n+1 \\ \end{array}$$

Notice that each row has length $i$ for $i=1,\ldots,n$ since the number of pairs with maximum element $i+1$ is $i$. Therefore the total number of pairs, which is $\binom{n+1}{2}$ is $\displaystyle \sum_{i=1}^n i$.

$\endgroup$
  • 3
    $\begingroup$ I doubt the person who downvoted this post will see this, but if you do, I would appreciate it in the future if you left an explanation as to why it was downvoted so that I could fix my post. $\endgroup$ – jgon May 8 '15 at 18:30
1
$\begingroup$

If you want to choose a pair out of $n+1$ objects (for example, $\{0,1,\dots,n\}$), the possibilities are:

$\{0,1\}$, $\{0,2\}$, ..., $\{0,n\}$, giving $n$ possibilities.

$\{1,2\}$, $\{1,3\}$, ..., $\{1,n\}$ giving $n-1$ possibilities. (note that we've already picked $\{1,0\}$, so we can't repeat it here)

$\{2,3\}$, $\{2,4\}$, ..., $\{2,n\}$ giving $n-2$ possibilities.

$\ \ \ \ \vdots$

$\{n-2,n-1\}$, $\{n-2,n\}$ giving $2$ possibilities.

$\{n-1,n\}$ giving $1$ possibility.

So the number of pairs is $n+(n-1)+\dots+2+1$

$\endgroup$
  • $\begingroup$ @jgon Oh, I missed that. Thanks $\endgroup$ – Kitegi May 9 '15 at 8:16
0
$\begingroup$

Start with $n+1$ objects, labelled $1,\dots,n+1$. We count the number of ways of choosing a pair of objects. We may always assume that the first object we choose has a lower number than the second.

Choose object number $1$. How many ways are there to choose a second object with a higher number?

Choose object number $2$. How many ways are there to choose a second object with a higher number?

Choose object number $3$. How many ways are there to choose a second object with a higher number?

$$ \dots $$

Choose object number $n$. How many ways are there to choose a second object with a higher number?

Choose object number $n+1$. How many ways are there to choose a second object with a higher number?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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