Discrete Mathematics for Computer Science

Program Correctness 57 computes the value of the expression on the right-hand side of the equal sign and then stores the result ...

58 CHAPTER 1 Sets, Proof Templates, and Induction 1.8.2 An Algorithm to Generate Perfect Squares We now demonstrate how you can ...

Program Correctness 59 RESULT: Approximation of v/-1 Root = 4 DecimalPlace Value = 1 for i = I to 8 do DecimalPlace Value = Deci ...

60 CHAPTER 1 Sets, Proof Templates, and Induction The process continues to add decimal digits to the intial approximation for as ...

Program Correctness 61 RESULT: Approximation of hi Root = 4 for i = 1 to 4 do Root = (Root + 17/Root)/2 print Root The computati ...

62 CHAPTER 1 Sets, Proof Templates, and Induction Therefore, 0 E T. (Inductive step) The remainder of the proof is left as an ex ...

Exercises 63 Find the smallest n E N such that 2n^2 + 3n + 1 < n^3. Prove by induction for n > 0: 2+4+6+...+2n =n^2 +n Pr ...

64 CHAPTER 1 Sets, Proof Templates, and Induction (c) Fo + F 3 + + F 3 = F 3 n+ 2 /2 for n > 0 (d)F 1 =Fn " - (-1)n forn > ...

Exercises 65 on all the money you owed during the month, and then your payment is subtracted. So, An+, = An(1 + I) - P Prove by ...

66 CHAPTER 1 Sets, Proof Templates, and Induction Refer to the Square Root II algorithm. (a) Finish the proof of Theorem 5. (b) ...

Strong Form of Mathematical Induction 67 for some prime numbers P1, P2 ...- Pk. The pi's are not required to be distinct, and k ...

68 CHAPTER 1 Sets, Proof Templates, and Induction Inductive step Base step no0 n0+1 n0+2 ni - base cases___________________ __ A ...

Strong Form of Mathematical Induction 69 n = pi "P2""Pi Aqlj q2...qj so n can be factored into a product of primes. Therefore, n ...

70 CHAPTER 1 Sets, Proof Templates, and Induction Constructing a proof by induction using the Strong Form of Induction requires ...

Strong Form of Mathematical Induction 71 In practice, you may often try to work out the Inductive step first. You will then see ...

72 CHAPTER 1 Sets, Proof Templates, and Induction cents or greater, we conjecture that all amounts except 1, 2, 4, 5, 7, 8, 10, ...

Strong Form of Mathematical Induction 73 INPUT: A nonzero real number x and a natural number n OUTPUT: The value of xn FastPower ...

74 CHAPTER 1 Sets, Proof Templates, and Induction FastPower (2, 5) \return^32 base expont call: 2 5 \return 32 base expont call ...

Strong Form of Mathematical Induction 75 arithmetic of numbers up to approximately 300 digits. These chips essentially compute p ...

76 CHAPTER 1 Sets, Proof Templates, and Induction the value N/2k, where 2 k is the highest power of 2 that is a factor of N, wil ...