# Math Help - Combinatorial Proof

1. ## Combinatorial Proof

Provide a combinatorial proof of the following identity:

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

I can provide an algebraic proof of the above identity. It is rather straight forward. But I have no idea how can I provide a "combinatorial" proof for the above identity! Please help!

Thanks!

2. May not be a best answer but here is an attempt

Consider a set A with 'n' elements, A = {a1,a2.....,an}
Consider a set B with 'n+1' elements, B = A + {x} = {a1,a2.....,an,x} - Here 'x' will have a special meaning for us.

Now you RHS = n^2 is simply the number of ways you can arrange 'n' elements from set A in 2 seats. repititions are allowed.

Now there is another way to count the same.
Select two elements from set B. i.e. (n+1)C2 ways.
Here in a selection, if we get element 'x' in the selection we interpret is as a repeat. So, for us {x,a1} gets mapped to {a1,a1}
But here we have missed a few cases for e.g. we counted {a1,a2} but did not count {a2,a1} [as we are using only selections]. So we need to add that
Now note the order will not matter when there is a repeatition. So excluding element 'x' there are nC2 selection. Which need to added to get the final answer.

So we get
(n+1)C2 + nC2 = n^2

It is easy to check that any pair like (a,b) is counted same number of times in LHS and RHS.
if a = b;
RHS count = 1
Now this pair can't come in the second selection, so it is counted only once (as {a,x} order doesn' matter)
similarly you can show if a<>b each is counted twice.

Hope this helps - maybe someone can show a more elegant way to put it though.

3. Infact you can give a better argument by breaking the arrangement in two cases
(1) Repeat
(2) No repeat

(1) can be done in nC1 ways.
(2) = 2. nC2
so n^2 = nC1 + 2. nC2
and simplify from here

4. Here is another approach.

Consider the set of ordered pairs $(x, y)$ where x and y are integers with $1 \leq x \leq n$ and $1 \leq y \leq n$. There are $n^2$ ordered pairs in the set.

Break the set into two subsets: (1) those with $x < y$ and (2) those with $y \geq x$.

Subset (1) contains $\binom{n}{2}$ ordered pairs.

In subset (2), we have $y \geq x$, which is equivalent to $x-1 < y$ since x and y are integers. So we have $0 \leq x-1 < y \leq n$, and there are $\binom{n+1}{2}$ possible ordered pairs.

So...

5. A question:

What is binomial expression that should be instead of ****

when ****=n^k

You understand me?

6. Originally Posted by Also sprach Zarathustra
A question:
What is binomial expression that should be instead of ****
when ****=n^k
You understand me?
I cannot say that I do understand your question.
But this is true:
$n^k = \sum\limits_{j = 0}^k {\binom{k}{j} \left( {n - 1} \right)^j }$.

7. Originally Posted by Also sprach Zarathustra
A question:

What is binomial expression that should be instead of ****

when ****=n^k

You understand me?

$\sum_{i=0}^k i! \; S(k,i) \binom{n}{i} = n^k$

where $S(k,i)$ is a Sterling number of the second kind.

8. Originally Posted by lpd
Provide a combinatorial proof of the following identity:

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

I can provide an algebraic proof of the above identity. It is rather straight forward. But I have no idea how can I provide a "combinatorial" proof for the above identity! Please help!

Thanks!
$\binom{n}{2}$ is the number of selections of 2 from n.

$\binom{n+1}{2}$ is the number of selections of 2 from n+1.

Before we bring in that extra term, there are $\binom{n}{2}$ selections.

When we bring in that extra term, there are an additional "n" selections of 2,
since that extra term can be paired with any of the original n,
along with all the original pairs.

Hence $\binom{n+1}{2}=\binom{n}{2}+n$

Therefore, the question is, is $2\binom{n}{2}+n=n^2\ ?$

$n^2=n(n)=n(n-1+1)=n(n-1)+n$

$2\binom{n}{2}=n(n-1)\ ?$

For pairs of 2, the number of arrangements is twice the number of selections etc..