5
$\begingroup$

Verify that for $n \geq 4$ $$\dbinom{n+1}{4} = \frac{\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)}{3}$$

Now present a combinatoric argument for the above.

First, by verify does it mean check for some n > 3? if so, then n = 4 gives both sides value 5. I have tried expanding both sides and It just gets messy, but i'm sure that would be attempting to prove it?

I cant quite move ahead with this one, I have said that $\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)$ is the number of ways of choosing 2 pairs of objects from n objects. my reasoning for this is that $\dbinom{n}{2}$ is the number of ways of choosing 2 objects from n and hence $\left(\substack{\binom{n}{2}\\{\displaystyle2}}\right)$ is the number of ways of choosing 2 of these ways... What i am struggling to do is understand how the three comes into it.

$\endgroup$
  • $\begingroup$ I think, in this case, "verify" means to prove algebraically, by manipulating the right hand side until it looks like the left. $\endgroup$ – Theo Bendit Jul 17 '15 at 18:08
  • $\begingroup$ Please don't use display math in titles; it takes too much vertical space on the front page. $\endgroup$ – Rahul Jul 17 '15 at 18:09
  • 1
    $\begingroup$ Hints: (1) How are two pairs of two things like one quadruple of things? (2) What if both pairs contain a common element? These are two independent hints. $\endgroup$ – Rahul Jul 17 '15 at 18:12
  • $\begingroup$ before reading the answer below fully and do the bad thing, i would like to take your comment into consideration and work it out for myself. (1) A pair of things is like one quadruple of things when each pair are disjoint, two pairs of things are not like a quadruple of things when they have a common member. so to expand, if i have four objects a,b,c,d. there are three ways i can choose distinct pairs from these four objects. [ab][cd], [bc][ad], [ac][bd]. Now concerning (2), i am struggling to use this hint at the moment. $\endgroup$ – user197848 Jul 17 '15 at 18:47
5
$\begingroup$

"Verify" would mean verify algebraically (using formulas such as $\binom{n+1}{4}=\frac{(n+1)n(n-1)(n-2)}{24}$. It's not that hard if you just consider the factorizations of each side. However, there is a nice combinatorial argument. $\left(\substack{{\binom{n}{2}}\\{\displaystyle 2}}\right)$ is the number of ways to pick two pairs of elements from a set of $n$; we can combine these pairs, and if an element is common to both pairs, then treat one of the instances of the element as a new $(n+1)$-st element. This counts the number of ways to pick 4 elements from a set of $n+1$. However, note that all ways to pick 4 are counted exactly 3 times, so you must divide by 3 to get the equality that is desired.

$\endgroup$
1
$\begingroup$

To verify:

$${n\choose2} = \frac{n(n-1)}{2}$$

$${\frac{n(n-1)}{2}\choose2} = \frac{\frac{n(n-1)}{2}.(\frac{n(n-1)}{2}-1)}{2}$$

$${\frac{n(n-1)}{2}\choose2} = \frac{n(n-1).(n^2-n-2)}{8} = \frac{(n+1)n(n-1)(n-2)}{8}\tag1 - RHS$$

$$ {(n+1)\choose4} = \frac{(n+1)n(n-1)(n-2)}{4!} = \frac{RHS}{3}$$

Hence proved.

$\endgroup$
  • $\begingroup$ AH i see where it went all wrong for me. thanks :) $\endgroup$ – user197848 Jul 17 '15 at 18:20
  • $\begingroup$ You are welcome. See the other responder's answer for a combintorial argument. It makes sense. Good luck $\endgroup$ – Satish Ramanathan Jul 17 '15 at 18:22
0
$\begingroup$

Using \begin{align} \binom{n}{2} = \frac{n(n-1)}{2} \end{align} then \begin{align} \frac{1}{3} \, \binom{\binom{n}{2}}{2} &= \frac{1}{2} \binom{n}{2} \, \left(\frac{n}{2} - 1\right) \\ &= \frac{n(n-1)}{4!} \left( n(n-1)-2 \right) = \frac{(n+1)(n)(n-1)(n-2)}{4!} \\ &= \binom{n+1}{4}. \end{align}


As to the modified component of the question: The comments seem to be helpful

$\endgroup$
0
$\begingroup$

Algebraic Manipulation is actually not that bad. $\binom{n}{2}=n(n-1)/2$, so $$\binom{\binom{n}{2}}{2}=\binom{n(n-1)/2}{2}=(n(n-1)/2)(n(n-1)/2-1)/6=n(n-1)(n^2-n-2)/24=n(n-1)(n+1)(n-2)/24=(n+1)!/4!(n-3)!=\binom{n+1}{4}$$

$\endgroup$

Your Answer

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