in Combinatory retagged by
4 votes
4 votes

Consider the following two combinatorial identities:

  1. For all $\mathrm{k}, \mathrm{n} \in \mathrm{N}$ with $\mathrm{k} \leq \mathrm{n}$,$$\left(\begin{array}{l} n \\ 2 \end{array}\right)+\left(\begin{array}{c} n+1 \\ 2 \end{array}\right)=n^{2} .$$
  2. For all $k, n \in N$ with $k \leq n$, $$k\left(\begin{array}{l} n\\ k \end{array}\right)=n\left(\begin{array}{l} n-1\\ k-1 \end{array}\right)$$

Which of the above are correct?

  1. Only $1$
  2. Only $2$
  3. Both
  4. None
in Combinatory retagged by

2 Answers

2 votes
2 votes
  1. We can verify algebraically that the identity holds: $$\left(\begin{array}{l}n \\2\end{array}\right)+\left(\begin{array}{c}n+1 \\2\end{array}\right)=\frac{n(n-1)}{2}+\frac{n(n+1)}{2}=n^{2}$$


  1. Algebraically, this identity is rather immediate. For a combinatorial perspective, consider the task of selecting a cabinet of $k$ people with a president out of $n$ possible candidates. One can either
    1. Select the president in $n$ ways and the remaining $k-1$ members of the cabinet in $\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ ways for a total of $n\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ ways.
    2. Or select the $k$ members of the cabinet first in $\left(\begin{array}{l}n \\ k\end{array}\right)$ ways and then the president among those in the cabinet in $k$ ways for a total of $k\left(\begin{array}{l}n \\ k\end{array}\right)$ ways.

edited by


For second one we can proof is like ,


$\large k\binom{n}{k}=\frac{k.n!}{k!(n-k)!}$


$\large n\binom{n-1}{k-1}=\frac{n.(n-1)!}{(k-1)!(n-1-k+1)!}$

                  =$\large \frac{k.n!}{k.(k-1)!(n-k)!}$

                   =$\large \frac{k.n!}{k!(n-k)!}$ =LHS


@GO Classes What could be a combinatorial argument for the first part?

0 votes
0 votes
Great question. Great answers already by many.

Combinatorial argument for 1.

This answer is plagiarized from so I deserve no credit at all. Just here to explain.

n^2 is the no. of integers less than 100.

2C(n, 2) : is the no. of numbers less than 100 having distinct digits.

C(n,1): is the no. of numbers less than hundred having both digits same.

Therefore,. n^2 = 2C(n, 2) + C(n,1)

                    n^2 = 2C(n,2) + n.

Now coming to the real part.

Our question,

                   C(n, 2) + C( n+1, 2 ) = n^2

                   C(n,2) + C( n+1, 2 ) = 2C(n, 2) + n.

                   C( n+1, 2) = C(n, 2) + n. (we will prove that this is true.)


C( n+1, 2) = no. of edges in a n+1 complete graph.


C(n, 2) + n = no. of edges between n nodes + put another node and join it with all n nodes.

Therefore we have proved that,

            C( n+1, 2 )= C(n, 2) + n.

And hence

            C(n,2)+ C(n+1, 2) = n^2 is true.

1 comment

$n^2$ is the number of non-negative integers less than $100 \equiv$ number of $2$ digit numbers with leading $0s$ allowed $\implies n = 10$.

Case $1$ : with distinct digits $= {n \choose 2} * 2!$.

Case $2$ : with same digits $= {n \choose 1}$.

Therefore, $n^2 = 2{n \choose 2} + {n \choose 1}$.

This part was not clear from your solution.


Related questions