Transcript Mixed Recursion: Sec. 8.4

Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the
Towers of Hanoi problem, Mn = 2n – 1, can
be proved by mathematical induction.
You might be wondering at this point,
“What’s mathematical induction?”
I’m so glad you asked!
Mixed Recursion: Sec. 8.4
Mathematical Induction
Mathematical induction is a technique often
used for proving formulas that involve
counting numbers (1, 2, 3, …).
This technique requires two steps.
Mixed Recursion: Sec. 8.4
Mathematical Induction
Step 1: Prove that the formula works for a
specific case—typically for the number 1.
Step 2: Assume the formula works for some
number, k. Based on that assumption, show
that it also works for k + 1.
Mixed Recursion: Sec. 8.4
Mathematical Induction
If you can show that the formula works for a
specific case, and that if it works for one
natural number it will work for the next
natural number, then you have proven that
the formula will work for all natural
numbers.
Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the Towers of Hanoi
problem, Mn = 2n – 1, can be proved by mathematical
induction.
a. What initial step is necessary?
First we must show that the formula works for
a specific case, such as for n = 1.
M1 = 21 – 1 = 2 – 1 = 1
This tells us that having one disc should
require one move, which is true.
Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the Towers of Hanoi
problem, Mn = 2n – 1, can be proved by mathematical
induction.
b. The proof assumes that the formula works
for a puzzle with k disks and then attempts
to prove the formula must also work for a
puzzle with k + 1 disks. Rewrite the
assumption and goal of the induction
proof in terms of the formula.
Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the Towers of Hanoi
problem, Mn = 2n – 1, can be proved by mathematical
induction.
b. Write the assumption and the goal.
Assumption: Mk = 2k – 1
Goal: Mk+1 = 2k+1 – 1
Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the Towers of Hanoi
problem, Mn = 2n – 1, can be proved by mathematical
induction.
c. Show how the proof is completed by
applying the recurrence relation.
We know the recurrence relation is
Mn = 2Mn-1 + 1
Apply that recursion to our assumption.
Mixed Recursion: Sec. 8.4
Exercise 3. The closed-form formula for the Towers of Hanoi
problem, Mn = 2n – 1, can be proved by mathematical
induction.
c. Show how the proof is completed by applying the
recurrence relation.
Assumption: Mk = 2k – 1
Applying our recursion:
Mk+1 = 2(2k – 1) + 1
Mixed Recursion: Sec. 8.4
Exercise 3. c. Show how the proof is completed by applying
the recurrence relation.
Goal: Mk+1 = 2k+1 – 1
So far we have: Mk+1 = 2(2k – 1) + 1
Distribute the first 2:
Mk+1 = 2(2k) + 2(-1) + 1 = 2k+1 – 2 + 1
Mk+1 = 2k+1 – 1  Our Goal!
Mixed Recursion: Sec. 8.4
Exercise 7. To help him finish his final year of college, Sam
took out a loan of $5,000. At the end of the first year
after he graduated, there was a $4,500 balance, and at the
end of the second year, $3,950 remained. The amount of
money left at the end of n years can be modeled by the
mixed recurrence relation tn = atn-1 + b.
a. The information stated above is summarized in the
following table:
n
0
1
2
tn
5,000
4,500
3,900
Mixed Recursion: Sec. 8.4
Exercise 7.
Please note there is a mistake in the book. The answers in the
back of the book for this problem would be correct if t2
were 3,950, instead of 3,900. We’ll proceed with the
values given in the table, and our answers will be
different from those in the back of the book.
n
0
1
2
tn
5,000
4,500
3,900
Mixed Recursion: Sec. 8.4
Exercise 7. a. Use the general form of a mixed recurrence
relation and the data in the table to write a system of
equations. Solve for a and b. What is the recurrence
relation for the amount of money in Sam’s account after
n years?
General form: tn = atn-1 + b
For n = 1: 4,500 = a(5,000) + b
For n = 2: 3,900 = a(4,500) + b
Mixed Recursion: Sec. 8.4
Exercise 7. a. What is the recurrence relation for the amount
of money in Sam’s account after n years?
For n = 1: 4,500 = a(5,000) + b
For n = 2: 3,900 = a(4,500) + b
We can solve this using matrices:
5,000 1
4,500 1


X
a 
b 
 
4,500
= 

3
,
900


Mixed Recursion: Sec. 8.4
Exercise 7. a. What is the recurrence relation for the amount
of money in Sam’s account after n years?
5,000 1
4,500 1


5,000 1 -1
5,000 1
4,500 1 X 4,500 1




a 
b 
 
X
a 
b 
 
X
a 
b 
 
4,500
= 

3
,
900


=
5,000 1 -1
4,500 1


 1.2 
=


1,500


So for the balance: tn = 1.2tn-1 – 1,500
4,500
X 

3
,
900


Mixed Recursion: Sec. 8.4
Exercise 7. a. What is the recurrence relation for the amount
of money in Sam’s account after n years?
We could also solve this by looking at the ratio of successive
1st differences:
n
0
1
2
tn
5,000
4,500
3,900
1st Diff
Ratio of Diff
-500
-600
1.2
Mixed Recursion: Sec. 8.4
Exercise 7. a. What is the recurrence relation for the amount
of money in Sam’s account after n years?
n
0
1
2
tn
5,000
4,500
3,900
1st Diff
Ratio of Diff
-500
-600
1.2
Multiply 1.2 times the first balance of 5,000 and we get
6,000. From there we need to subtract 1,500 in order to
get to the second balance of 4,500. Thus,
tn = 1.2tn-1 - 1500
Mixed Recursion: Sec. 8.4
Exercise 7. b. What will be the balance owed on the loan at
the end of the third year? The fourth year?
Recurrence relation: tn = 1.2tn-1 – 1,500
End of second year: t2 = $3,900
End of third year: t3 = 1.2(3,900) – 1,500 = $3,180
End of fourth year: t4 = 1.2(3,180) – 1,500 = $2,316
Mixed Recursion: Sec. 8.4
Exercise 7. c. What is the rate of interest on this loan?
tn = 1.2tn-1 – 1,500
The value of a, which in this case is 1.2, tells us the interest
rate. Take that value and subtract 1, which gives us .2,
and then multiply by 100 to get the percent.
.2(100) = 20% interest
Mixed Recursion: Sec. 8.4
Exercise 7. d. Find the fixed point for this recurrence relation. What is the
significance of this amount of money?
tn = 1.2tn-1 – 1,500
x = 1.2x – 1,500
Subtract x from each side, and add 1,500 to each side.
1,500 = .2x
Divide each side by .2, or multiply each side by 5.
7,500 = x
If the original balance were $7,500, the loan would never be paid off. The
$1,500 payment each year would exactly cover the interest.
Mixed Recursion: Sec. 8.4
Exercise 8. Suppose a college’s tuition over the past 3 years
has risen from $8,000 to $8,700 to the present cost of
$9,435. Use a mixed recurrence relation of the form
tn = atn-1 + b to predict next year’s tuition.
n
1
2
3
tn
8,000
8,700
9,435
1st Diff
Ratio of Diff
700
735
1.05
Mixed Recursion: Sec. 8.4
Exercise 8. Use a mixed recurrence relation of the form
tn = atn-1 + b to predict next year’s tuition.
n
1
2
3
tn
8,000
8,700
9,435
1st Diff
Ratio of Diff
700
735
1.05
Multiply 8,000 by 1.05 to get 8,400. We need to add 300 to
reach the year 2 value of 8,700. So our recurrence relation is
tn = 1.05tn-1 + 300
This leads us to predict next year’s tuition as 1.05(9,435) +
300, or $10,206.75.