Homework 2
Document last modified: 

1. Exercises 2.3-3, 2.3-4, 2.3-6

   For the recurrence:

   T(2) = 2

   T(n) = 2T(n/2) + n if n=2^k, for k>1

   Hint: 2.3-3

   Assume: T(2^k) = 2^k lg 2^k

   ^Show:      T(2^k+1) = 2^k+1 lg 2^k+1

    

2. Suppose you take out a mortgage for M dollars at a monthly interest rate I and a monthly payment P: (To calculate I : if the annual interest rate is 12%, divide by 12 to get a monthly rate of 1%, then replace the percentage with the decimal fraction 0.01.) Let A_n denote the amount you have left to pay after n months. So, A₀ = M by definition. At the end of each month, you are first charged interest on all the money you owed during the month and then your payment is subtracted.

   The amount left can be defined by the recurrence equation:

   A_n+1  = A_n (1 + I) - P

   The closed-end formula is:

   A_n  = (M - P/I)(1+I)ⁿ+P/I

   1. Calculate the monthly payment on some real loan at current interest rates over a fairly long period of payments. Show equation used and answer.

      To calculate the monthly payment on a 30-year loan of $100,000 at 12% interest per year (12% makes the math easier, monthly interest is 0.12/12 = 0.01) requires the key insight that after 30 years for:

      A_n  = (M - P/I)(1+I)ⁿ+P/I

      A₃₆₀  = (100,000 - P/0.01)(1+0.01)³⁶⁰+P/0.01 = 0

      and solve for P. This is not exact because of rounding to whole cents.
       

   2. Prove by induction:

   A_n  = (M - P/I)(1+I)ⁿ+P/I

   This looks a little worse but is solved the same as those in class.

Turn in

1. Cover sheet with your name, C455, date, and Homework 2.
2. Typed answers.