1
$\begingroup$

I am attempting to prove that for some non-negative integers p ≥ q ≥ r, ${p \choose r} \geqslant {q \choose r}$.

My base cases were p=q=r=0 and p=q=r=1, and my induction hypothesis is to assume that the statement holds for some arbitrary non-negative values of p, q, and r. I get stuck, of course, at the inductive step. Right now I have:

Consider p + 1, q + 1, e.g. ${p+1 \choose r} ≥ {q+1 \choose r}$ I'm attempting to use Pascal's Identity and the fact that ${(r - 1)! = \frac{r!}{r}}$, but I end up with a very circular argument, where I'm saying that

From ${p+1 \choose r} \geqslant {(q+1) \choose r}$ we get ${p \choose r} + {p \choose r-1} ≥ {q \choose r} + {q \choose r-1}$

then $$\frac{p!}{r!(p-r)!} + \frac{p!}{(r-1)!(p-r-1)!} ≥ \frac{q!}{r!(q-r)!}+\frac{q!}{(r-1)!(q-r-1)!}$$

And here's where I get stuck, because if this equation reduces to $${p+1 \choose r} \geqslant {q+1 \choose r}$$ then I've just shown something that was a given, and I need to change my inductive step to be more robust? Or would this be sufficient, and I'm overthinking it?

Thank you in advance!

$\endgroup$
4
  • $\begingroup$ Thanks, I edited it to fix that error. $\endgroup$ Oct 28 '20 at 16:42
  • $\begingroup$ I don't understand what you mean by passing those two expressions to the other half. Would that be at the step with factorials? $\endgroup$ Oct 28 '20 at 16:49
  • $\begingroup$ sorry, I overlooked that $r$ is fixed, pardon ! $\endgroup$
    – G Cab
    Oct 28 '20 at 16:56
  • $\begingroup$ All good! I appreciate you looking it over!!! I've run around in circles on it this evening $\endgroup$ Oct 28 '20 at 17:04
1
$\begingroup$

It seems like you're not familiar with double (or even triple) induction. That's fine, you can still induct on 1 variable.

The approach I would take is to show that for a fixed $r$, and for any $ q \geq r$, then we have

$$ { q + 1 \choose r } \geq { q \choose r }. $$

This can be done directly (via comparing the expansion which you wrote), which is my preference. Or it can done via induction (via the binomial identity which you wrote) if you want an induction proof.

Once this is proved, we see that for any $ p \geq q \geq r$, we get the chain of inequalities

$${ p \choose r } \geq { p-1 \choose r } \geq {p-2 \choose r } \geq \ldots \geq {q+1 \choose r } \geq { q \choose r }. $$

$\endgroup$
1
$\begingroup$

Hint:

$$ \eqalign{ & 0 \le r \le q \le p\quad \Rightarrow \quad {{q^{\,\underline {\,r\,} } } \over {r!}} \le {{p^{\,\underline {\,r\,} } } \over {r!}}\quad \Rightarrow \quad q^{\,\underline {\,r\,} } \le p^{\,\underline {\,r\,} } \quad \Rightarrow \cr & \Rightarrow \quad \left( {q + 1} \right)q^{\,\underline {\,r\,} } = \left( {q + 1} \right)^{\,\underline {\,r + 1\,} } \le \left( {p + 1} \right)^{\,\underline {\,r + 1\,} } = \left( {p + 1} \right)p^{\,\underline {\,r\,} } \quad \Rightarrow \cr & \Rightarrow \quad \left( {q + n} \right)^{\,\underline {\,r + n\,} } \le \left( {p + n} \right)^{\,\underline {\,r + n\,} } \cr} $$

so we are moving diagonally up ...

$\endgroup$

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.