2
$\begingroup$

It is true that $$\binom{\binom{n}{2}}{2} = 3\binom{f(n)}{4}$$for some function $f(n)$. What is $f(n)$?


Since there's a function involved, I can't really so it using a counting argument, and I don't know how to solve this kind of problem algebraically. Solutions are greatly appreciated.

$\endgroup$
2
$\begingroup$

Let $y = f(n).$ We have: $$LHS = \frac{1}{8}(n-1) n (n-2)(n+1)$$ and $$RHS = \frac{1}{8}y(y-1)(y-2)(y-3).$$

$\endgroup$
  • $\begingroup$ After simplifying, I got $n(n-1)(n+1)(n+2)=y(y-1)(y-2)(y-3)$ what should I do next? I don't know how to simplify it anymore. $\endgroup$ – Dreamer Oct 7 '16 at 20:44
  • $\begingroup$ @Regina What patterns do you notice here? If you have to guess a solution what would it be $\endgroup$ – trang1618 Oct 7 '16 at 20:45
  • $\begingroup$ $x+1$? Perhaps? $\endgroup$ – Dreamer Oct 7 '16 at 20:50
  • $\begingroup$ @Regina Yup. $f(n) = y = n+1$ would work for all $n$. This is also stated in the other answer by JeanMarie. $\endgroup$ – trang1618 Oct 7 '16 at 20:52
3
$\begingroup$

This can be solved using a counting argument.

Suppose you have the $n$ numbers $1,2, \dots n$ and a special marker $M$.

Of these $n+1$, you choose 4 and try to form two sets of two numbers from $\{1, 2, \dots, n\}$.

If you pick $M$ and three numbers $a_1, a_2, a_3$, then you can do $\{a_1, a_2\}, \{a_2, a_3\}$ etc (3 ways).

If you don't pick $M$, then you can do $\{a_1, a_2\}, \{a_3, a_4\}$ etc giving 3 different such possibilities.

This gives you that $$\binom{\binom{n}{2}}{2} = 3 \binom{n+1}{4}$$

$\endgroup$
  • $\begingroup$ Very interesting proof [+1] $\endgroup$ – Jean Marie Oct 8 '16 at 8:30
2
$\begingroup$

The identity (valid only for $n>3$) is

$$\binom{\binom{n}{2}}{2} = 3\binom{n+1}{4}$$

i.e., plainly $f(n)=n+1$.

It is a consequence of the identity:

$$\dfrac{\frac{n(n-1)}{2}\left(\frac{n(n-1)}{2} - 1\right)}{2} = 3\dfrac{(n + 1)n(n - 1)(n - 2)}{24}$$

valid for any $n$.

$\endgroup$
  • $\begingroup$ It's valid for all $n$, not just $n > 3$, modulo the convention that $\binom{n}{k} = 0$ for $n < k$. $\endgroup$ – anomaly Oct 7 '16 at 20:47
  • $\begingroup$ I wanted to stick to the usual (combinatorial) definition of binomial coefficients where $\binom{n}{k}$ is defined iff $n \geq k$. I amaware that there are extensions of this definition, but I don't know the level of the OP : if he is in high school, he will have the combinatorial definition of $\binom{n}{k}$. $\endgroup$ – Jean Marie Oct 7 '16 at 20:50
  • 1
    $\begingroup$ I suppose that using the usual definition of binomial coefficients, this is the only possible answer. What is interesting to notice, from an algebraic point of view, is that the quartic equation in $f$ shows four simple solutions since the problem ends to solve $(f-2+n)(f-1-n)(f^2-3f-n+n^2)=0$. For once the quartic can be simply solve, I thought it was worth to mention. Cheers. $\endgroup$ – Claude Leibovici Oct 8 '16 at 6:08
  • $\begingroup$ @Claude Leibovici Valuable remark ! $\endgroup$ – Jean Marie Oct 8 '16 at 6:31
  • 1
    $\begingroup$ @ClaudeLeibovici, $f(x) = {x \choose 4}$ has an axis of symmetry, and your (very nice) observation is equivalent to the statement that when $f(x)=a$ has a rational root, the symmetry provides a second rational root. $\endgroup$ – zyx Oct 8 '16 at 7:31

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.