1
$\begingroup$

I have to show that $$(n-j)! \leq \frac{n!}{(j+1)!}$$

I tried to develop $(n-j!)$ as $\frac{n!}{n(n-1)\cdot\cdot\cdot(n-j+1)}$ but I have no clue after that because I end up with $$\frac{1}{n(n-1)\cdot\cdot\cdot(n-j+1)} \leq \frac{1}{(j+1)!}$$

$${n(n-1)\cdot\cdot\cdot(n-j+1)} \geq {(j+1)!}$$

$\endgroup$
1
  • 1
    $\begingroup$ It's not true for $j=n$. $\endgroup$ – Thomas Andrews Oct 18 '17 at 18:09
0
$\begingroup$

You could also just induct on $n$. The base case for $n = j+1$ is easy. The induction step isn't difficult either, as $$ (n+1-j)! = (n+1-j) (n-j)! \leq (n+1-j) \frac{n!}{(j+1)!} \leq (n+1) \frac{n!}{(j+1)!} = \frac{(n+1)!}{(j+1)!}. $$

$\endgroup$
2
$\begingroup$

If $j\geq 0$ and $j<n$ then $n+1 \leq {n+1\choose j+1}$, thus

$$1\leq {1\over n+1}{n+1\choose j+1} = {n! \over (j+1)!(n-j)!}$$

$\endgroup$
9
  • 1
    $\begingroup$ It might also be useful to not that $n+1=\binom{n+1}{1}$, to make the first inequality more obvious. $\endgroup$ – Thomas Andrews Oct 18 '17 at 18:09
  • 1
    $\begingroup$ why $\binom{n+1}{1} \leq \binom{n+1}{j+1}$ $\endgroup$ – Rom Oct 18 '17 at 18:11
  • $\begingroup$ Well it is kind of empirical fact, take a look at a Pascal triangle. $\endgroup$ – Aqua Oct 18 '17 at 18:15
  • $\begingroup$ Let $F$ be a family of all $j$ element subset of set $M=\{1,2,....,n\}$. For each element in $F$ let $m$ be minimum and $M$ maximum of this element. Now we have a surjective map $f:F\to M$ which takes $X$ to $m$ if $m<j$ and other vise to M. Thus $|M|\geq |F|$. $\endgroup$ – Aqua Oct 18 '17 at 18:26
  • 1
    $\begingroup$ That's why must be $j<n$ ? $\endgroup$ – Rom Oct 18 '17 at 18:35

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.