D(1) = 1,d(n) = n.d(n-1) for n ≥ 2

Question

asked Feb 11, 2023 177k views

1 Answer

Shreemaan Abhishek · Answer 1 · 2023-02-17T02:40:44+0000

Assuming you're solving for
d(n) , we have by substitution

$d(n) = n d(n-1) \implies d(n-1) = (n-1) d(n-2) \\\\ ~~~~ \implies d(n) = n(n-1)d(n-2)$

$d(n) = n d(n-1) \implies d(n-2) = (n-2) d(n-3) \\\\ ~~~~ \implies d(n) = n(n-1)(n-2)d(n-3)$

$d(n) = n d(n-1) \implies d(n-3) = (n-3) d(n-4) \\\\ ~~~~ \implies d(n) = n(n-1)(n-2)(n-3) d(n-4)$

and so on. After
iterations of this, we have the pattern

$d(n) = n(n-1)(n-2)\cdots(n-(k-3))(n-(k-2))(n-(k-1)) d(n-k)$

so that after
k=n-1 iterations,

$d(n) = n(n-1)(n-2)\cdots(n-(n-3))(n-(n-2)) d(n-(n-1)) \\\\ ~~~~= n(n-1)(n-2)\cdots3\cdot2\,d(1) \\\\ ~~~~ = \boxed{n!}$