# Solve T(n) = T(n-1)*n with repeated substitution [duplicate]

I'm trying to solve T(n) = T(n-1)*n using repeated substitution.

I can expand it, but I'm having trouble with geometric sequences for any problem. I find I'm just memorizing solutions to typical problems. It's sometimes hard for me to go from the expanded equation to a general equation that I can simplify.

T(n) = T(n-1)(n)

T(n) = T(n-2)(n-1)(n)

T(n) = T(n- 3)(n-2)(n-1)(n)

I'm not sure how to generalize this to ultimately find the big O. Any tips are appreciated!

This is the rucursive formula for $n$ factorial.
Define the formula $T(n)$ for $n \geq 0$ as $T(n) = nT(n-1)$. By repeated substitutions observe that $$T(0) = 1$$ $$T(1) = 1\times T(0)=1 \times 1$$ $$T(2) = 2 \times T(1)=2\times 1\times 1$$ $$T(3) = 3\times T(2)=3\times 2\times 1\times 1$$ $$\dots$$ $$T(n) = nT(n-1)=n\times (n-1)(n-2)\dots 1\times 1$$ Thus by simple observation you can easily guess the pattern of product of the first $n$ positive integers.
For a complete proof you need to prove that $T(n) = n!$. This is easily done by induction. For $n=0$, $T(n)=1 = 0!$. Assume that formula is true for $n-1$. Then $T(n)=nT(n-1)=n(n-1)!=n!$ which completes the proof. So $T(n)$ is $\Theta(n!)$.
• $T(0) = 1, T(n)=2T(n-1)$
• $T(0) = 1, T(n) = nT(n-2)$, for only even $n$s.