2

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.

Rocco
  • 23
  • 1
    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$. –  Feb 21 '15 at 23:40
  • @Ahmed: It’s not clear that $\binom{n}j>j$ for $j<n$ is something that Rocco is allowed to assume at this point. – Brian M. Scott Feb 21 '15 at 23:47
  • Yes @BrianM.Scott, I'm just talking about the idea. –  Feb 21 '15 at 23:50

2 Answers2

2

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$.

Brian M. Scott
  • 616,228
0

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!$.
Bernard
  • 175,478