1

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)

Mike Spivey
  • 55,550
Paulo Argolo
  • 4,210

5 Answers5

7

The binomial coefficients are Unimodal.

Aryabhata
  • 82,206
  • 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. – Mike Spivey Nov 18 '10 at 22: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$.

Shai Covo
  • 24,077
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.

Larry Denenberg
  • 721
  • 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). – Mike Spivey Nov 19 '10 at 18:24
  • 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. – Larry Denenberg Nov 23 '10 at 18:02
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".

Bill Dubuque
  • 272,048
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.

user02138
  • 17,064