Proving $\frac{n^n}{e^{n-1}} 2$. I am trying to prove 

$$\frac{n^n}{e^{n-1}}<n!<\frac{(n+1)^{n+1}}{e^{n}} \text{ for all }n > 2.$$ 

Here is the original source (Problem 1B, on page 12 of PDF)
Can this be proved by induction?
The base step $n=3$ is proved: $\frac {27}{e^2} < 6 < \frac{256}{e^3}$ (since $e^2 > 5$ and $e^3 < 27$, respectively).
I can assume the case for $n=k$ is true: $\frac{k^k}{e^{k-1}}<k!<\frac{(k+1)^{k+1}}{e^{k}}$.
For $n=k+1$, I am having trouble:
\begin{align}
(k+1)!&=(k+1)k!\\&>(k+1)\frac{k^k}{e^{k-1}}\\&=e(k+1)\frac{k^k}{e^{k}} 
\end{align}
Now, by graphing on a calculator, I found it true that $ek^k >(k+1)^k$ (which would complete the proof for the left inequality), but is there some way to prove this relation?
And for the other side of the inequality, I am also having some trouble:
\begin{align}
(k+1)!&=(k+1)k!\\&<(k+1)\frac{(k+1)^{k+1}}{e^{k}}\\&=\frac{(k+1)^{k+2}}{e^k}\\&<\frac{(k+2)^{k+2}}{e^k}.
\end{align}
I can't seem to obtain the $e^{k+1}$ in the denominator, needed to complete the induction proof.

Some times it is easier for such an induction if we shift the sequence by one step, so the basis of the expressions is nicer for algebraic manipulations.
Let's rewrite your sequence of inequalities as
$$ \displaystyle  {n! \over e}<{(n+1)^{n+1} \over e^{n+1}} < {(n+1)! \over e}
<{(n+2)^{n+2} \over e^{n+2}}< {(n+2)! \over e} \tag 1  $$
and for simpler references below as
$$ a_0 \quad < \quad b_0 \quad  <\quad a_1 \quad  <\quad b_1  \quad < \quad a_2  \tag 2$$
Then we ask: does from $a_0<b_0<a_1$ follow that $a_1<b_1<a_2$   ?     
Of course $a_1 = (n+1) \cdot a_0$ and so it might be useful to define $b_0$ as a fraction in the interval of $a_0$ and $a_1$: 
$$ b_0 = (n+1)q_1 \cdot a_0 \text{ where } q_1<1 \tag {3.1 }$$. Consequently, define $$ b_1 = (n+2)q_2 \cdot a_1 \text{ where also } q_2<1  \tag {3.2 }$$
Here the inequality $q_2 < 1$ is not known but expected and if this can be shown by induction from $q_1$ this would solve the problem .                         
So we start with $$q_1 = {b_0 \over a_0 (n+1)} = {(n+1)^{n} \over e^n n! } \tag {4.1 } $$
and by the beginning of the induction we know, that this is indeed smaller than 1 so $$q_1 < 1 \tag {4.2 }$$
Now we have simply $$q_2 = {b_1 \over a_1 (n+2)} = {(n+2)^{n+1} \over e^{n+1} (n+1)! } \tag {4.3 }$$
Next we consider the systematic progression in the sequence of $q_1,q_2,q_3,...$. To begin we determine the ratio $r_2={q_2 \over q_1}$ . We find
$$ \begin{eqnarray} r_2&=&{q_2 \over q_1}& =&{ {(n+2)^{n+1}  \over  e^{n+1} (n+1)! } \over
    {(n+1)^{n}  \over  e^{n} (n)! } }  \\
&&&=& {(n+2)^{n+1} e^{n} (n)! \over  e^{n+1} (n+1)! (n+1)^{n}} \\
&&&=& {(n+2)^{n+1}   \over  e  (n+1)^{n+1}} \\
&&&=&  \left({n+2   \over  n+1}\right)^{n+1} \cdot \frac 1e \\
r_2&=&{q_2 \over q_1}& =&   \left( 1 + {1 \over  n+1} \right)^{n+1} \cdot \frac 1e \end{eqnarray} \tag {5.1 }$$
It is now needed to recognize/remember from the definition of $e$, that the last expression is smaller than 1 and that for $n \to \infty$ approximates monotonically 1.
Also we see by the expansion of the binomial-series $(1+1/x)^x=1+1+1/2+...$ in the general case that for $x>2$ this is greater than $2$ so $${2 \over e} \approx 0.73 < r_2 < 1  \tag{5.2}$$
From this we know now, that $q_2$ is not only smaller than $1$ but also smaller than $q_1$ but$q_{n+1} \to q_n$ for increasing $n$.           
So we have
 $$  \begin{eqnarray} &q_2 &=& q_1 \cdot r_2 < q_1 < 1 \\
   \to& b_1 &<& (n+2) a_1 = a_2 \\
 \to &a_1 &<& b_1 <a_2  \end{eqnarray} \tag {6 }$$
which we wanted to show. 
