Induction proof with binomial coefficients and inequalities 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!
 A: 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 }. $$
A: 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 ...
