MATH135 Lecture Notes - Lecture 4: Mathematical Induction
14 May 2018
School
Department
Course
Professor
MATH 135 Fall 2015: Extra Practice Set 4
These problems are for extra practice and are not to be handed. Solutions will not be posted but, unlike
assignment problems, they may discussed in depth on Piazza.
•The warm-up exercises are intended to be fairly quick and easy to solve. If you are unsure about any
of them, then you should review your notes and possibly speak to an instructor before beginning the
corresponding assignment.
•The recommended problems supplement the practice gained by doing the corresponding assignment.
Some should be done as the material is learned and the rest can be left for exam preparation.
•A few more challenging extra problems are also included for students wishing to push themselves
even harder. Do not worry if you cannot solve these more difficult problems.
Warm-up Exercises
1. Evaluate
8
X
i=3
2iand
5
Y
j=1
j
3.
Recommended Problems
1. Prove the following statements by simple induction.
(a) For all n∈N,
n
X
i=1
(2i−1) = n2.
(b) For all n∈N,
n
X
i=0
ri=1−rn+1
1−rwhere ris any real number such that r6= 1. .
(c) For all n∈N,
n
X
i=1
i
(i+ 1)! = 1 −1
(n+ 1)!.
(d) For all n∈N,
n
X
i=1
i
2i= 2 −n+ 2
2n.
(e) For all n∈Nwhere n≥4, n!> n2.
2. Prove the following statements by strong induction.
(a) A sequence {xn}is defined recursively by x1= 8, x2= 32 and xi= 2xi−1+ 3xi−2for i≥3. For
all n∈N,xn= 2 ×(−1)n+ 10 ×3n−1.
(b) A sequence {tn}is defined recursively by tn= 2tn−1+nfor all integers n > 1. The first term
is t1= 2. For all n∈N,tn= 5 ×2n−1−2−n.
40
MATH135 Full Course Notes
Verified Note
40 documents
Document Summary
Math 135 fall 2015: extra practice set 4. These problems are for extra practice and are not to be handed. Solutions will not be posted but, unlike assignment problems, they may discussed in depth on piazza: the warm-up exercises are intended to be fairly quick and easy to solve. If you are unsure about any of them, then you should review your notes and possibly speak to an instructor before beginning the corresponding assignment: the recommended problems supplement the practice gained by doing the corresponding assignment. Some should be done as the material is learned and the rest can be left for exam preparation: a few more challenging extra problems are also included for students wishing to push themselves even harder. Do not worry if you cannot solve these more di cult problems. Recommended problems: prove the following statements by simple induction. (a) for all n n, (b) for all n n, n.
