CIS 1910 Lecture Notes - Lecture 20: Negative Number, Well-Order, Mathematical Induction

• School: University of Guelph
• Department: Computing and Information Science
• Course: CIS 1910
• Professor: Luiza Antonie

Document Summary

Theorem: for every positive integer n, 3 evenly divides 22n-1. The inductive step: suppose that for positive integer k, 3 evenly divides 22k-1, we show that: 3 evenly divides 22(k+1)-1. By inductive hypothesis, 3 evenly divides 22k-1 which means that 22(k+1)-1 = 3 x m for some integer m. Gn = 3 x gn-1 +2n for any n 1. Gn = 5/2 x 3n n 3/2. There are two components of an inductive proof: G0 = 5/2 x 30 0 3/2 = 1. Gk = 5/2 x 3k k 3/2. By definition of the recurrence relation, gk+1 = 3 x gk + 2(k+1) for any k 1. = 3x(5/2 x 3k k 3/2) + 2(k+1) (by induction hypothesis) = 5/2 x 3 x 3k 3k 3 x 3/2 + 2k + 2. = 5/2 x 3(k+1) (k+1) 3/2. Therefore, gk+1 = 5/2 x 3(k+1) (k+1) 3/2. Suppose we wanted to prove an upper bound on the fibonacci sequence.