Example 2 Bob the banker lends money at an outrageous rate of interest. He demands to be paid 10% interest per week on a loan, compounded weekly. Suppose you borrow 500 from Bob. If you wait for 4 weeks to pay him back, how much will you owe? Let M(n) be how much money you owe Bob on the nth week. Initially you owe, Solution: 500 so M(0)=500. How much will you owe at the end of week 1 ? How much will you owe at the end of week 2 ? How much will you owe at the end of week 3 ? How much will you owe at the end of week 4 ? Can you write down a recurrence relation for M(n)? We could now do a top-down computation to find M(4). A certain person put a pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is supposed that every month each pair begets a new pair which from the second month on becomes productive? Let F(n) represent the number of pairs of rabbits present on month n. What is F(1) ? Assuming that it takes two months for the first pair of rabbits to become productive, wha is F(2) ? Compute F(3),F(4) and F(5),F(6)