home—info—lectures—hws—exams
hw09
sums, induction
reading about structural induction, recursion
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.
-
p.162 #18a-c.
(5ed p.236 #18a-c) variant:
replace "3" with "300" and "2" with "200".
Leave your answer as arithmetic (e.g. 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 over1
(Put another way: it doesn't matter which order you do additions in.)
-
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)=“12+22+...+n2 = 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)?
- Show P(1) is true, completing the base case.
- What is the inductive hypothesis?
- What do you need to prove in the inductive step?
- Complete the inductive step.
- Explain why these steps show
the formula holds for all postive integers n.
-
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)?
- Show P(7) is true, completing the base case.
- What is the inductive hypothesis?
- What do you need to prove in the inductive step?
- Complete the inductive step.
- Explain why these steps show
the formula holds for all postive integers n ≥7.
-
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(0)=1; f(n+1)=3f(n).
-
f(0)=1; f(n+1)=2f(n).
-
f(0)=1; f(n+1)=(f(n))²+f(n)+1.
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).
1...at least if the index set
is finite. ↩
home—info—lectures—hws—exams