9
$\begingroup$

An exercise in the first chapter of Discrete Mathematics, Elementary and Beyond asks for a proof of the following identity:

$$ {n \choose 2} + {n+1 \choose 2} = n^2 $$

The algebraic solution is obvious to me, but less so the combinatorial logic. I think the right-hand side relates to choosing one of n elements twice in a row to produce a set of two elements, including the possibility of duplicate elements (for instance, one could choose the nth element twice in a row). However, given that the sets discussed thus far do contain duplicate elements, it's odd to then interpret n^2 as a representation of such a set. I'm not too sure what the two parts of the left side mean when taken together, either. How can I think about this intuitively based on the combinatorial meanings of the individual terms?

$\endgroup$
12
$\begingroup$

How many pairs of numbers $(k,j)$ are there for $1\leqslant j,k\leqslant n$? The obvious solution is $n^2$. The other solution is to count those with $k<j$ and those with $k\geqslant j$. The first number is seen to be $$\binom n2 $$ The second is $$\binom n2+\binom n1=\binom{n+1}2$$

Since choosing a subset of two elements of an $n+1$-sized set amounts to choosing either $2$ from the first $n$ elements or fixing $n+1$ and choosing one from the first $n$ elements.

(The geometric idea is that a square composed of $n^2$ little squares of size $1\times 1$ is a union of two triangles consisting of $\binom n2$ and $\binom{n+1}2$ little squares.)

$\endgroup$
  • 1
    $\begingroup$ What is the combinatorial argument that the latter number is $\binom{n+1}{2}$ ? $\endgroup$ – ShreevatsaR Apr 20 '14 at 23:51
  • $\begingroup$ @ShreevatsaR Is the above combinatorial enough? $\endgroup$ – Pedro Tamaroff Apr 20 '14 at 23:57
  • $\begingroup$ Yes, seems more satisfying now. :-) By the way, your geometric picture along with the proof that $1 + 2 + \dots + n = \binom{n + 1}{2}$ might make for an elegant version! $\endgroup$ – ShreevatsaR Apr 21 '14 at 3:40
  • $\begingroup$ This makes sense, thank you! My understanding of it now is that one needs $2{n \choose 2}$ to cover the possibilities of (a,b) and (b,a) as well as ${n \choose 1}$ to account for duplicate pairings like (a,a), which are only counted n times as opposed to the former since having their elements switched produces the same set. This gives $2{n \choose 2} + {n \choose 1}$, which simplifies to the left-hand side of the original identity. $\endgroup$ – user3145309 Apr 21 '14 at 4:09
2
$\begingroup$

$n^2$ is the number of non-negative integers less than $100_n$.

$2 {n \choose 2}$ is the number of non-negative integers with distinct digits less than $100_n$

${n \choose 1} = n$ is the number of non-negative integers with the same two digits less than $100_n$

Now, of course, we need an argument for ${n \choose 2} + n = {n + 1 \choose 2}$.

There are $n \choose 2$ ways to pick two elements from a set of $n$ elements. To find the number of ways to pick two elements from a set of $n+1$ elements, we include all of the possibilities from the $n$ subset along with each element of the $n$ subset paired up with the new element of the $n+1$ element.

$\endgroup$
1
$\begingroup$

I don't see any direct explanation for this identity, but I can see something very simple if you apply ${n+1 \choose 2} = {n\choose2} + {n \choose 1}$.

$${n \choose 2} + {n \choose 2} + {n \choose 1} = 2{n \choose 2} + {n \choose 1} + n^2$$

$n^2$ is the number of ways to select two elements from a set of $n$, allowing duplicates, and taking order into account. $n \choose 2$ is the number of ways to select two non-duplicates from $n$, but not taking order into account. Because we don't take order into account, we have to double to get the total number of ways to select two distinct elements. We then just have to take care of the case where we select the same element twice, which is $n\choose1$.

$\endgroup$
  • $\begingroup$ This is not gonna work, I don't think you can use that identity directly. $\endgroup$ – Yilun Zhang Apr 20 '14 at 23:50
  • $\begingroup$ @YilunZhang What do you mean? I'm just applying the well known recursive identity for binomial coefficients. $\endgroup$ – Jack M Apr 20 '14 at 23:52
  • $\begingroup$ But I think if you are using it, you need to explain that identity using a combinatorial proof as well. $\endgroup$ – Yilun Zhang Apr 20 '14 at 23:58
  • $\begingroup$ @YilunZhang Yes, which is quite easy. The standard proof is on the wiki article I linked. $\endgroup$ – Jack M Apr 20 '14 at 23:58
1
$\begingroup$

All the answers posted above is useful to a great extent. But, I am giving a visual proof (more than combinatorics).

What you want is $$\begin{align} &{n\choose 2}+{n+1\choose 2}=n^2\\ \implies&\frac {n(n-1)}2+\frac {(n+1)n}2=n^2\\ \implies&(1+2+\dots+(n-1))+(1+2+\dots+n)=n^2. \end{align}$$

Now, consider this square, colouring in this way. Here I am giving for $n=6$, it can be generalised easily, taking $n$-sided squares.

enter image description here

Here the number of coloured squares is $$\color{red}{6+5+4+3+2+1=\frac {6\times 7}2={6+1\choose 2}}.$$

Now colour the rest elements in this way,

enter image description here

So, here the number of coloured squares is $$\color{magenta}{5+4+3+2+1=\frac {5\times 6}2={6\choose 2}}.$$

And now, sum these up. What you get is

enter image description here

Here, the number of coloured squares is $$\color{blue}{6\times 6=6^2\text{[total number of squares]}}$$

So, ultimately, what we get is $${\color{red}{\text{no. of red coloured squares}}}+{\color{magenta}{\text{no. of pink coloured squares}}}={\color{blue}{\text{total number of squares}}}$$ $$\implies\color{red}{6+1\choose 2}+\color{magenta}{6\choose 2}=\color{blue}{6^2}$$

So, in generalised (taking $n$-sided squares), we have $$\implies\color{red}{n+1\choose 2}+\color{magenta}{n\choose 2}=\color{blue}{n^2}$$

$\endgroup$
0
$\begingroup$

Given n symbols, the number of ways that 2 locs can be filled, allowing repeats is n².

This can be divided into three groups. Firstly, C(n.2) pairs of basic 2-combinations. Secondly another C(n,2) identical, but reversed pairs plus n doubles.

To combine the last two groups we note that C(n+1,2) covers all of C(n,2) plus n pairs which include the extra symbol. If in each of these n pairs we replace the extra symbol by its companion, the result follows.

Hence n² = C(n,2) + C(n+1,2)

$\endgroup$
0
$\begingroup$

I believe you're looking for more of a proof...

n!/(2!(n-2)!) + (n+1)!/(2!(n+1-2)!) = n!/(2!(n-2)!) + (n+1)!/(2!(n-1)!) = n(n-1)(n-2)!/(2!(n-2)!) + (n+1)(n)(n-1)!/(2!(n-1)!) = n(n-1)/(2!) + n(n+1)/(2!) = (n^2-n)/2 + (n^2 + n)/2 = 2n^2/2 = n^2

Although it's not great to follow on this site, that shows the steps to prove why it works.

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