Due:
2007.Oct.30 (Tues).
You'll be allowed to re-work the problems up to Nov.02 (Fri)
if you have made thoughtful progress on them by Tues.
Although you are welcome to typeset your work nicely (using Microsoft Word
or LaTeX or whatever to get nice logic symbols),
it's probably much easier to write formulas by hand.
-
p.161 #13
(5ed p.236 #13).
You don't need to show your work.
- 20 (Notice this is the sum 1..6 minus 1, which we know is 6·7/2 minus 1.)
- 1+(-2)+4+(-8)+16 = 1+2+8=11
- 30
- Noting that 2-2=2·2-2=2, we see this is the sum of 2+2+...+2, which we recognize (via binary numerals) as 2-1 = 511.
-
p.162 #18a-c.
(5ed p.236 #18a-c) variant:
replace "3" with "300" and "2" with "200".
Leave your answer as arithmetic (⪚ your answer should include terms
like
200·301·150
,
but it should not include any …
-- only things
you can type into a calculator.)
You don't need to show your work.
(And if you do, clearly circle your answer.)
Hint:
Remember that you can distribute Sigma over addition/subtraction:
Σ(f(i)+g(i)) = (Σf(i))+(Σg(i)),
regardless of what values i ranges over...at least if the index set
is finite.
(Put another way: it doesn't matter which order you do additions in.)
-
Σi=1200
Σj=1300(i-j)
= (Σi=1200
Σj=1300i)
-
(Σi=1200
Σj=1300j)
=
(Σi=1200
(iΣj=13001))
-
(Σi=1200
301·300/2)
=
(Σi=1200300i)
-
(200·301·300/2)
=
(300·Σi=1200i)
-
(200·301·300/2)
=
(300·200·201/2)
-
(200·301·300/2)
=
300·200·(201-301)/2
=
-300·200·50
=
-3,000,000.
-
Σi=1200
Σj=1300(3i+2j)
= (Σi=1200
Σj=13003i)
+
(Σi=1200
Σj=13002j)
=
(Σi=1200
(3iΣj=13001))
+
(Σi=1200
(2Σj=1300j))
=
(Σi=1200
(3iΣj=13001))
+
(Σi=1200
(2·301·150)))
=
(Σi=1200900i)
+
(200·2·301·150)
=
(900·Σi=1200i)
+
(200·301·150)
=
(900·100·201)
+
(200·2·301·150)
-
Σi=1200
Σj=1300j
= Σi=1200(150·301)
= 200·150·301
-
p.280 #
53.
(5ed p.253 #7)
(I'll accept either #3 or #5.)
Using mathematical induction,
show that ∀n∈N.P(n),
where
P(n)=
1+2+...+n = n(n+1)(2n+1)/6
.
For all induction proofs:
Include each step (a) through (f),
as in last week's homework (= Rosen #4).
(Note that the base case might be P(1) or P(0) or P(7), depending.)
- What is P(1)?
1² = 1·(1+1)(2·1+1)/6
- Show P(1) is true, completing the base case.
Easy arithmetic:
1·(1+1)(2·1+1)/6 = 2·3/6 = 1 = 1²,
as desired.
- What is the inductive hypothesis?
P(k), which is
1+2+...+k = k(k+1)(2k+1)/6
- What do you need to prove in the inductive step?
P(k+1), which is
1+2+...+k+(k+1) = (k+1)(k+2)(2(k+1)+1)/6
- Complete the inductive step.
1+2+...+k = k(k+1)(2k+1)/6
inductive hypothesis
⇔
1+2+...+k +(k+1)
= k(k+1)(2k+1)/6 + (k+1)
add (k+1) to both sides of an equality
=
k(k+1)(2k+1)/6 + 6(k+1)(k+1)/6
algebra
=
[k(2k+1) + 6(k+1)](k+1)/6
factor out (k+1)/6
=
[2k+k + 6k+6](k+1)/6
algebra
=
[2k+7k+6](k+1)/6
algebra
=
[(2k+3)(k+2)](k+1)/6
algebra
=
(k+1)(k+2)(2(k+1)+1)/6
algebra
Thus we have a chain of equalities (line 2 through the last line):
1+2+...+k+(k+1) = (k+1)(k+2)(2(k+1)+1)/6,
which is exactly P(k+1).
- Explain why these steps show
∀n∈N+.P(n).
the formula holds for all postive integers n.
We showed P(1),
and we showed that ∀k.(P(k)→P(k+1)).
By the inference rule of mathematical induction, we can conclude
∀n.P(n) (for the domain of integers 0 or greater).
-
p.280 #20.
(5ed p.253 #12)
Using mathematical induction,
show that
∀n∈N,n≥7.P(n),
where P(n) = 3n < n!
.
(Note that n!
means n·(n-1)·(n-2)·...·2·1.
So 4! = 4·3·2·1· = 24.
It actually follows that 0!=1.)
For all induction proofs:
Include each step (a) through (f),
as in last week's homework (= Rosen #4).
(Note that the base case might be P(1) or P(0) or P(7), depending.)
- What is P(7)?
37< 7!
- Show P(7) is true, completing the base case.
Arithmetic:
37
= 34·33
= 81·27
< 90·28·2
< (3·5·6)·(4·7)·2
= 7!
as desired.
- What is the inductive hypothesis?
P(k) (where k≥7), which is
3k< k!
- What do you need to prove in the inductive step?
P(k+1), which is
3k+1< (k+1)!
- Complete the inductive step.
We show that P(k) → P(k+1):
3k< k!
inductive hypothesis
⇔
3·3k< 3·k!
multiply both sides by 3 preserves an inequality
⇔
3k+1< 3·k!
algebra
⇒
3k+1< 3·k!+(k+1-3)·k!
adding a positive amount to the larger side of an inequality
only strengthens it.
(We know it's positive since
k≥7 is enough to deduce that (k+1-3)≥5>0.)
Note that this step is not reversible.
(While it might be true that P(k+1)→P(k),
you can't just reverse the lines of this proof to get it.)
⇔
3k+1< (k+1)·k!
algebra
⇔
3k+1< (k+1)!
(recursive) def'n of (k+1)!
Thus we have concluded that
3k+1< (k+1)!
which is exactly P(k+1).
- Explain why these steps show
∀n≥7.P(n).
the formula holds for all postive integers n ≥7.
We showed P(7),
and we showed that ∀k≥7.(P(k)→P(k+1)).
By the inference rule of mathematical induction, we can conclude
∀n≥7.P(n).
-
Read lightly over sections 4.2, 4.3;
but paying close attention to:
-
the definition of extended binary trees and full binary trees
(Def'n 5,6)
-
structural induction on such trees (Def'n 7 and Th'm 2)
-
p.308 #1
(5ed p.270 #1)
-
f(0)=1; f(n+1)=f(n)+2.
f(1)=3; f(2)=5; f(3)=7; f(4)=9.
(In general, it seems like f(n)=2n+1. Can you prove this with induction?)
-
f(0)=1; f(n+1)=3f(n).
f(1)=3; f(2)=9; f(3)=27; f(4)=81.
(In general, it seems like f(n)=3. Can you prove this with induction?)
-
f(0)=1; f(n+1)=2f(n).
f(1)=2; f(2)=4; f(3)=16; f(4)=216=65536.
(In general, it seems like f(n)=22n. Can you prove this with induction?)
-
f(0)=1; f(n+1)=(f(n))²+f(n)+1.
f(1)=3; f(2)=13; f(3)=183; f(4)=183²+183+1=33673.
(What on earth might the general pattern be here?)
If you see a few other problems in Rosen which catch your eye,
and you'd like to do them for extra credit, you are welcome to
(though you can ask me for how much; extra-credit is harder to earn
point-per-point than regular credit).