ITEC 122 2007fall ibarland

home—info—lectures—hws—exams

hw09
sums, induction
reading about structural induction, recursion

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.

1. p.161 #13 (5ed p.236 #13). You don't need to show your work.
2. 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 over¹ (Put another way: it doesn't matter which order you do additions in.)
3. 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.)
   1. What is P(1)?
   2. Show P(1) is true, completing the base case.
   3. What is the inductive hypothesis?
   4. What do you need to prove in the inductive step?
   5. Complete the inductive step.
   6. Explain why these steps show the formula holds for all postive integers n.
4. p.280 #20. (5ed p.253 #12)
   Using mathematical induction, show that ∀n∈N,n≥7.P(n), where P(n) = “3ⁿ < 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.)
   1. What is P(7)?
   2. Show P(7) is true, completing the base case.
   3. What is the inductive hypothesis?
   4. What do you need to prove in the inductive step?
   5. Complete the inductive step.
   6. Explain why these steps show the formula holds for all postive integers n ≥7.
5. 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)
6. p.308 #1 (5ed p.270 #1)
   1. f(0)=1; f(n+1)=f(n)+2.
   2. f(0)=1; f(n+1)=3f(n).
   3. f(0)=1; f(n+1)=2^f(n).
   4. 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).

home—info—lectures—hws—exams

©2007, Ian Barland, Radford University Last modified 2007.Dec.17 (Mon)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu