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
 A: $a_5=  (\frac{5}{4})^4 \cdot   (\frac{4}{3})^3 \cdot (\frac{3}{2})^2 \cdot 2 \cdot 1
$
$\begin{array}\\
a_n
&=\prod_{k=2}^n (\frac{k}{k-1})^{k-1}\\
&=\dfrac{\prod_{k=2}^n k^{k-1}}{\prod_{k=2}^n (k-1)^{k-1}}\\
&=\dfrac{\prod_{k=2}^n k^{k-1}}{\prod_{k=1}^{n-1} k^k}\\
&=\dfrac{\prod_{k=2}^n k^{k-1}}{\prod_{k=1}^{n-1} kk^{k-1}}\\
&=\dfrac{\prod_{k=2}^n k^{k-1}}{\prod_{k=1}^{n-1} k\prod_{k=1}^{n-1} k^{k-1}}\\
&=\dfrac{n^{n-1}\prod_{k=2}^{n-1} k^{k-1}}{\prod_{k=1}^{n-1} k\prod_{k=2}^{n-1} k^{k-1}}\\
&=\dfrac{n^{n-1}}{(n-1)!}\\
&=\dfrac{n^{n}}{n!}\\
\end{array}
$
A: 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.
A: Let's have $\displaystyle b_n=\frac{n^n}{a_n}$
$\displaystyle b_{n+1}=\frac{(n+1)^{n+1}}{a_{n+1}}=\frac{(n+1)^n(n+1)}{(\frac{n+1}{n})^na_n}=(n+1)b_n$ this is the induction relation for factorial.
Since $b_1=a_1=1$ then $b_n=n!$
Finally $\quad\bbox[5px,border:1px solid]{\displaystyle a_n=\frac{n^n}{n!}}$
