$T(n) = nT(n − 1), T(1) = 1$ for $n ≥ 1$

Question

Hey I was wondering if anyone knows how to solve this recurrence relation by repeated substitution? $T(n) = nT(n − 1), T(1) = 1$ for $n ≥ 1$ Thanks.

Instead of speaking of "solve" I would rather say that there is a well known notation for the solution: $n!$ — drhab, Oct 17 '17 at 17:14

score 0 · Answer 1 · answered Oct 17 '17 at 17:15

0

It's $n!$, by definition

$T(1)=1$

$T(2)=2\times 1$

$T(3)=3\times 2\times 1$

$...$

$T(n)=n(n-1)!$

answered Oct 17 '17 at 17:15

Raffaele

score 0 · Answer 2 · answered Oct 17 '17 at 17:19

0

For $n\geq2$ $$T(n)\prod_{k=1}^{n-1}T(k)=\prod_{k=1}^nT(k)=n\prod_{k=1}^{n-1}kT(k)=n!\prod_{k=1}^{n-1}T(k),$$ which gives $T(n)=n!.$

answered Oct 17 '17 at 17:19

Michael Rozenberg

2 Answers2