1
$\begingroup$

How to prove the following theorem?

Theorem:

If the binomial numbers $C(n,p)$ and $C(n,q)$ are equal, with $p$ different from $q$, then $p+q = n$.

($n$, $p$ and $q$ are natural numbers)

5 Answers 5

7

The binomial coefficients are Unimodal.

  • 6
    Just thought I'd point out that Moron is giving a hint here, as not every unimodal triangle of numbers $R(n,p)$ has the property that $R(n,p) = R(n,q) \Rightarrow p+q=n$. You'll need to use some other properties of the binomial coefficients, too.2010-11-18
4

It is suffices to show that $q! (n-q)! = p! (n-p)!$ implies $p+q=n$ ($p \ne q$). Assume without loss of generality that $p > q$. Then, we need to show that $p!/q! = (n-q)!/(n-p)!$ implies $p+q=n$, or $(q+1) (q+2) \cdots p = (n-p+1) (n-p+2) \cdots (n-q)$ implies $p+q=n$. Since both sides of the last equality have identical number of terms ($p-q$), we must have $q+1 = n-p+1$, that is $p+q=n$.

2

Mike Spivey correctly points out that unimodality does not suffice. Here's a quick way to fill the gap: Consider the set $S = \{p,q,n-p,n-q\}$. Now $n\choose x$ assumes only one value for $x\in S$, by hypothesis and the fact that ${n\choose p}={n\choose n-p}$. But $p\neq q$ and $p+q\neq n$ together imply that $S$ has at least three distinct values. This plus unimodality gives a contradiction.

  • 0
    The usual definition of unimodality allows for consecutive numbers to take on the same value. (See, for instance, the link given in Moron's answer.) I believe your argument requires that the numbers be strictly increasing and then strictly decreasing. The binomial coefficients do have that property, but it still needs to be mentioned (or maybe even proved).2010-11-19
  • 0
    Right you are; I should have said something more like "strict unimodality" if there is such a thing. But the binomial coefficients don't qualify since ${2n+1\choose n}={2n+1\choose n+1}$. Although a single duplication at the top doesn't vitiate the argument. In any case, as you say, more work is necessary.2010-11-23
1

HINT $\ $ In order to prove that $\rm\ \binom{n}{p}\ =\ \binom{n}{q}\ \:\Rightarrow\ \ \ p+q = n\ \ \ if\ \ \ p \ne q\ \ $ for $\rm\ \ p,q\in [0, n]$

consider how to prove that $\rm\ \ \ sin(p)\ =\ sin(q)\ \Rightarrow\ p+q = \pi\ \ \ if\ \ \ p \ne q\ \ $ for $\rm\ \ p,q\in [0,\pi]$

MORAL $\ $ A proper choice of $\rm \:sin\:$ can get you "over the hump".

0

Suppose that for a fixed $n$ we have the equality $\binom{n}{p} = \binom{n}{q}$ with $p \neq q$. Observe that \begin{eqnarray} 0 = \frac{\pi}{2^{n-1}} \left[ \binom{n}{p} - \binom{n}{q} \right] = \int_{-\pi}^{\pi} \left( \cos (2p - n)x - \cos (2q - n)x \right) \ \cos^{n} x \ dx. \end{eqnarray} The cosine difference identity \begin{eqnarray} \cos A - \cos B = -2 \sin (\tfrac{A + B}{2}) \ \sin (\tfrac{A - B}{2}) \end{eqnarray} implies \begin{eqnarray} \int_{-\pi}^{\pi} \left( \sin (p + q - n)x \ \sin (p- q)x \right) \ \cos^{n} x \ dx = 0 . \end{eqnarray} I'll leave it as an exercise to finish the proof and conclude the result.