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.
 A: 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$.
A: 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!$.

