Consider the following recurrence relation Hn 0 if n lessth

Consider the following recurrence relation: H(n) = {0 if n lessthanorequalto 0 1 if n = 1 or n = 2 H(n - 1) + H(n - 2) - H(n - 3) if n > 2. Compute H(n) for n 1. 2, .... 10. Using the pattern from pan (a), guess what H(100) is. Consider the recurrence relation defined in Example .3.3 (FROM TEXT BOOK, also discussed in class and shown in slides) Suppose that, as in the example, you borrow $500 but you pay her back $100 each week. Each week. Ursula charges you 10% interest on the amount you still owe. after your $100 payment is taken into account Write down a recurrence relation for M(n), the amount owed after n weeks. How much will you owe after four weeks?

Solution

Given:

H(n) = 0 if n <= 0

H(n) = 1 if n = 1, or n = 2

H(n) = H(n-1) + H(n-2) + H(n-3) if n > 2

1. a. Compute H(n) for n = 1, 2, ... , 10.

H(1) = 1

H(2) = 1

H(3) = 2

H(4) = 4

H(5) = 7

H(6) = 13

H(7) = 24

H(8) = 44

H(9) = 81

H(10) = 149

b. Using the pattern from part (a), guess what H(100) is. As the number is growing exponentially, it will be really hard to predict, and even calculate.