# Induction Proof with Factorials

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.

• 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$. – user207710 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. – user207710 Feb 21 '15 at 23:50

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!$.
• Ahh, induction on $n$. Silly me! – Rocco Feb 22 '15 at 0:16

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

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