0
$\begingroup$

Prove that for every $n$,$i$ $\in$ $\mathbb{N}$ if $0$$\leq$$i$$\leq$$n$ then ${{n}\choose{i}}$$=$${{n}\choose{n-i}}$. Secondly, prove that if $i$$<$$j$$\leq$$n\over2$ then ${{n}\choose{i}}$$<$${{n}\choose{j}}$.

According to me, the first one is trivially true by expanding ${{n}\choose{n-i}}$ to get to ${{n}\choose{i}}$ (Is that correct though?). Concerning the second part, here's what I did: $($$i$$<$$j$$\leq$$n\over2$$)$ $\longrightarrow$ $($$-i$$>$$-j$$\geq$$-$$n\over2$$)$ $\longrightarrow$ $($$n-i$$>$$n-j$$\geq$$n$$-$$n\over2$$)$ $\longrightarrow$ $($$n-i$$>$$n-j$$\geq$$n\over2$$\geq$$j$$>$$i$$)$. This is where I got stuck when trying to prove:

$(n-i)$$!$$i$$!$ $>$ $(n-j)$$!$$j$$!$ since:

$n!\over{(n-i)!i!}$ $<$ $n!\over{(n-j)!j!}$ $\iff$ $(n-i)$$!$$i$$!$ $>$ $(n-j)$$!$$j$$!$

$\endgroup$
1
$\begingroup$

Thus, we need to prove that: $$(n-i)(n-i-1)...(n-i-j+1)>(n-j)(n-j-1)...(n-j-i+1),$$

which is true because $n-i>n-j$.

$\endgroup$
  • $\begingroup$ Shouldn't the last ones be: $(n-i-j-1)$ and $(n-j-i-1)$ ? $\endgroup$ – Slavik Egorov Oct 5 '17 at 10:37
  • $\begingroup$ @Slavik Egorov No! $n-i$, $n-i-1$,...,$n-i-j+1$ they are $j$ numbers exactly. But $n-i$, $n-i-1$,...,$n-i-j-1$ they are $j+2$ numbers. $\endgroup$ – Michael Rozenberg Oct 5 '17 at 10:40
0
$\begingroup$

Let's say we proved this for a row $n$. Then, for $i\leq\tfrac n2$, we know $${n\choose i-2}<{n\choose i-1}<{n \choose i}$$ and so adding them gives us

$${n\choose i-2}+{n\choose i-1}<{n\choose i-1}+{n \choose i}$$ so that $${n+1\choose i-1}<{n+1\choose i}$$ which, by induction, proves that ${n+1\choose i}<{n+1\choose j}$ for $i<j\leq \frac n2$. This is not enough however, because we need the edge case $j=\frac{n+1}{2}$. Not to spoil everything for you, try to look at pascals triangle and see why the middle number is larger than its neighbours in even rows. Look at the row above it and try to express your ideas into mathematical reasonings.

$\endgroup$
  • $\begingroup$ I might be missing something, but why is ${{n}\choose{i-2}}$ $<$ ${{n}\choose{i-1}}$ $<$ ${{n}\choose{i}}$ correct? $\endgroup$ – Slavik Egorov Oct 5 '17 at 12:00
  • $\begingroup$ That's what you assume. I'm inexplicitly using induction here. Together with a base case, this is a solid proof. $\endgroup$ – vrugtehagel Oct 5 '17 at 12:28

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.