From $a_{n+1}=(1+ \frac{1}{n})^n \cdot a_n$ to $a_n$ to be proven by induction 
Find and Prove by induction an explicit formula for $a_n$ if $a_1=1$ and for $n \geq 1$
  $$a_{n+1}=(1+ \frac{1}{n})^n \cdot a_n$$

Checking the pattern:
$$a_1=1$$
$$a_2= 2 \cdot 1$$
$$a_3= (\frac{3}{2})^2 \cdot 2 \cdot 1$$
$$a_4= (\frac{4}{3})^3 \cdot (\frac{3}{2})^2 \cdot 2 \cdot 1$$
$$a_5=  (\frac{5}{4})^4 \cdot   (\frac{4}{3})^3 \cdot (\frac{3}{2})^2 \cdot 2 \cdot 1$$
I can see the general pattern in the index as $(...)^{(n-1)!}$
and I am tempted to state that it is $( \frac{n!}{(n-1)!})^{(n-1)!}
$
Should this be correct, I do not see the factorial manipulation that allow me to write this.
Otherwise, what would the formula be? What would the approach be?
Much appreciated

Rewrite:
$$\frac{a_{n+1}}{(n+1)^{n+1}}=\frac{a_n}{n^n} . \frac{1}{n+1}$$
Thus:
$$\frac{a_{n+1}}{(n+1)^{n+1}}=\frac{a_n}{n^n}.\frac{1}{n+1} 
=\frac{a_{n-1}}{n^{n-1}}.\frac{1}{n}.\frac{1}{n+1}
=\frac{a_{n-2}}{n^{n-2}}.\frac{1}{n-1}.\frac{1}{n}.\frac{1}{n+1}$$
$$=...$$
$$=\frac{a_1}{1}.\frac{1}{(n+1)!}$$
Therefore:
$$a_{n+1}=\frac{(n+1)^{n+1}}{(n+1)!}$$
Of course once you know the result you can use induction to prove it.
