From $a_{n+1}=(1+ \frac{1}{n})^n \cdot a_n$ to $a_n$ to be proven by induction

Question

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

Answer 1

$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} $

Answer 2

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.

Answer 3

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!}}$