1

How can I solve the following recursive relation:

t(n)=(n-1)*t(n-1)

where the base case is

t(1)=1

Is it okay just saying that:

t(2)=1!
t(3)=(3-1)t(2)=2!
t(4)=(4-1)t(3)=3!
t(5)=4!
and so on...t(n)=(n-1)!

and after prove this by induction? Any ideas?

KeykoYume
  • 492
  • 1
    With an appropriate "prove by induction" it looks like you've got the right idea. Could you clarify your question? – abiessu Mar 23 '15 at 22:10

2 Answers2

1

for $n \ge 1$ $$ \frac{t(n+1)}{t(n)} = n $$ so $$ t(n+1) = \prod_{k=n}^1 \frac{t(k+1)}{t(k)} = \prod_{k=n}^1 k = n! $$

David Holden
  • 18,040
1

Well, you have observed something correct, that $t(n)=(n-1)!$. It's not a proof yet though and making a table doesn't really make progress towards a proof, beyond being able to have a reasonable hypothesis to prove.

All you need to note is that $$t(1)=0!$$ and then it's clear that if $t(n)=(n-1)!$ then $t(n+1)=n!$, since $t(n+1)=n\cdot t(n)$ which would be $n\cdot (n-1)!=n!$.

Milo Brandt
  • 60,888