Solve $T(n) = n \cdot T(n-1)$

Question

Can someone please help with this?

Solve $T(n) = T(n-1)\cdot n$ by iteration method.

I will appreciate it if it is explained step by step

Answer 1

Denote $a:=T(0)$ , the initial value.

Then, we have $T(n)=a\cdot n!$

Proof by induction

$n=0:$ $T(n)=T(0)=a=a\cdot 0!$

$n\rightarrow n+1:$ $T(n+1)=a\cdot (n+1)!=(a\cdot n!)\cdot (n+1)=T(n)\cdot (n+1)$ , which coincides with the formula we get if we plug $n+1$ into $T(n)=T(n-1)\cdot n$.

You can guess the formula by looking at the first few values

$$T(0)=a$$

$$T(1)=T(0)\cdot 1=a$$

$$T(2)=T(1)\cdot 2=2\cdot a$$

$$T(3)=T(2)\cdot 3=3\cdot 2\cdot a$$

$$T(4)=T(3)\cdot 4=4\cdot 3\cdot 2\cdot a$$

The pattern can easily be seen.

Answer 2

For $n=1$ you have $T(1)=T(0)$ This imply by the iteration you want to $$T(2)=2T(1)\Rightarrow T(3)=3T(2)=3\cdot2T(1)\Rightarrow T(4)=4\cdot3\cdot2T(1)$$ and so on so you get $$T(n)=n!T(1)$$

Obviously you need an initial value $T(1)=T(0)$.

This way corresponds to the iteration you want to apply but you can prove also by immediate induction the result you have got.