reset password
Author Message
wveit
Posts: 18
Posted 13:23 Apr 04, 2018 |

Hi, does anyone know what the correct answer is for HW A1 - Section 2 #10?

Also, can anyone describe briefly or provide a link with explanation of how to solve this problem?

Thanks!

Attachments:
cysun
Posts: 2935
Posted 13:30 Apr 04, 2018 |

T(1) = 1

T(2) = 2*T(1) = 2*1 = 2!

T(3) = 3*T(2) = 3*2! = 3!

...

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

marrawi
Posts: 21
Posted 13:33 Apr 04, 2018 |

Perform Back substitution

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

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

2- T(n-2)= n*(n-1) + n*(n-2) +T(n-3) ...........

So it’s n! Therefore none of the above choice

rabbott
Posts: 1649
Posted 14:16 Apr 04, 2018 |

The two answers above perform some substitutions and then "notice" that the answer is that T(n) = n!.

The problem statement itself let's you do that. T(n) is defined exactly as you would define f(n) when defining factorial:

f(1) = 1

f(n) = n * f(n-1)

So by "pattern recognition" one can say that T == f == factorial.

But noticing that T is the same as factorial isn't a strategy for solving the problem.

Alternatively, if one hypothesized that T = factorial, one could prove it inductively. But again, one must start with the hypothesis that T = factorial and then confirm it.

I don't know a mechanical strategy for arriving at the idea that T = factorial.

  • Here's a brief summary of recurrence relations. 
     
  • Here's a website that solves recurrence relations. 
Last edited by rabbott at 14:17 Apr 04, 2018.
wveit
Posts: 18
Posted 19:29 Apr 04, 2018 |

Thanks everyone for your help to solve that by different methods. I can't believe I didn't see that was n!. That linked document looks excellent for reviewing recurrence in general, thank you!