1
$\begingroup$

Problem: If $0 \leq j \leq n-1$, then $(j+1)!(n-j)!\leq n!$.

The hint is to use induction and a symmetry argument.

Attempt:

Base step for induction ($j=0$): $(0+1)!(n-0)! = n! \leq n!$

Induction step: Suppose the induction hypothesis holds for $j < n-1$. We know

$(j+1)!(n-j)!\leq n!$

$(j+2)!(n-j)!\leq (j+2)n!$

$(j+2)!(n-(j+1))!\leq \frac{(j+2)n!}{n-j}$.

But I am not sure what else to do... Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Though it's required by induction, it's nice to see that this inequality is equivalent to: $n \choose j$ $> j$ which is true because $n > j$. $\endgroup$ – user207710 Feb 21 '15 at 23:40
  • $\begingroup$ @Ahmed: It’s not clear that $\binom{n}j>j$ for $j<n$ is something that Rocco is allowed to assume at this point. $\endgroup$ – Brian M. Scott Feb 21 '15 at 23:47
  • $\begingroup$ Yes @BrianM.Scott, I'm just talking about the idea. $\endgroup$ – user207710 Feb 21 '15 at 23:50
0
$\begingroup$

Use induction on $n$.

We'll have to prove that if $\,0\le j\le n$, then $\,(j+1)\mkern1.5mu!\,(n+1-j)\mkern1.5mu!\le (n+1)\mkern1.5mu! $

  • If $j\le n-1$, by the inductive hypothesis we can write: $$(j+1)\mkern1.5mu!\,(n+1-j)\mkern1.5mu!=(j+1)\mkern1.5mu!\,(n-j)\mkern1.5mu!\,(n+1-j)\le n\mkern1.5mu!\,(n+1-j)\le (n+1)\mkern1.5mu!$$
  • If $j=n$ we have: $\, (j+1)\mkern1.5mu!\,(n+1-j)\mkern1.5mu!= (n+1)\mkern1.5mu!$.
$\endgroup$
  • $\begingroup$ Ahh, induction on $n$. Silly me! $\endgroup$ – Rocco Feb 22 '15 at 0:16
1
$\begingroup$

I wouldn’t use induction, and since it’s only a hint, you’re probably not required to do so. I’d begin by dividing both sides by $j!$ to rewrite the inequality as

$$j+1\le\binom{n}j\;.\tag{1}$$

This is easily checked for $j=0$; you’ve essentially done this in your base step. Thus, I might as well assume that $1\le j\le n-1$. By pairing up a subset of $\{1,\ldots,n\}$ with its complement, we see that $\binom{n}j=\binom{n}{n-j}$. (This may be the symmetry idea mentioned in the hint.) Thus, $(1)$ is equivalent to

$$j+1\le\binom{n}{n-j}\;.$$

This says that $\{1,\ldots,n\}$ has at least $j+1$ subsets of size $n-j$. And that’s true. To see this, let $A$ be a subset of size $n-j$. Since $j<n$, $A$ is not empty, and I can pick an $a\in A$. For each $k\in\{1,\ldots,n\}\setminus A$ let $A_k=(A\setminus\{a\})\cup\{k\}$, the set obtained by removing $a$ from $A$ and replacing it with $k$. Show that these sets, together with $A$ itself, are $j+1$ distinct subsets of $A$ of size $n-j$.

$\endgroup$
  • $\begingroup$ Thank you for this argument. It is very clear and easy to follow. $\endgroup$ – Rocco Feb 22 '15 at 0:17
  • $\begingroup$ @Rocco: You're welcome. $\endgroup$ – Brian M. Scott Feb 22 '15 at 0:26

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.