ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

hw10
induction

1. (10pts) p.280 #3 (5ed p.253 #7)
   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).
   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.
2. (10pts) 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.)
   
   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.
3. (8pts) p.308 #1 (5ed p.270 #1): Compute f(1)..f(4), when:
   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.
4. 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)

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Dec.15 (Mon)

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