real analysis - Prove the sequence $a_{n} = frac{n^{n}}{n!}$ is not bounded above

Prove the sequence is $a_{n} = \frac{n^{n}}{n!}$ not bounded above.

This is exercise 1.4.2 in Introduction to Analysis by Arthur P. Mattuck.

The hint given in the book is "Show that $a_{n} > n$".

I attempted to show this using induction.

Basic Step

$a_{1} = \frac{1^{1}}{1} = 1 \not > 1$

$a_{2} = \frac{2^{2}}{2} = 2 \not > 2$

$a_{3} = \frac{3^{3}}{3} = \frac{9}{2} > 3$

Inductive Step

Show $\frac{n^{n}}{n!} > n \implies \frac{(n+1)^{(n+1)}}{(n+1)!} > n+1$

This is where I get stuck.

I reduced the sequence so $\frac{(n+1)^{(n+1)}}{(n+1)!} = \frac{(n+1)^{n}}{n!}$.

I figure the next step is to show $\frac{(n+1)^{n}}{n!} > \frac{n^{n}}{n!} + 1$, but I am not sure how to get there.

I also looked at this question since it was working with a similar equation, but I wasn't able to derive anything out of the discussion that could lead to an answer.

Edit:

Side Question

Does this need to be solved using induction, or are there other methods of directly proving this result? Is induction a clumsy or unwieldy tool for this problem?

Answer

$$a_n=\frac{n\cdot n\cdots n}{1\cdot 2\cdots n}=\frac{n}{1}\frac{n}{2}\cdots\frac{n}{n}>\frac{n}{1}=n$$