Discrete Math Fall 2017 Homework 7 Due: Friday, November 10, 2017 The below problems involve material from Chapter 5. You must type your solutions. Submit a single PDF file on eLC by 9PM on the given due date and include your name and 810 number. You must show all work performed for the questions below. For the inductive proofs you must do the following: State the base case P(b), indicating the integer b used as the base. Complete the base case. State the inductive hypothesis. Complete the inductive step, indicating where the inductive hypothesis was used. In your solutions, you must clearly identify each of the above items. Each question is worth 10 points. 1. Find and prove by induction a formula for Pn 1 i=1 i(i+1) for all positive integers n. 2. Use induction to prove that 2 + 2(7) + 2(7)2 + . . . + 2(7)n = integer n. 1(7)n+1 4 3. Use induction to prove that (1.2.3) + (2.3.4) + . . . + (n.(n + 1).(n + 2)) = positive integer n. for every nonnegative n(n+1)(n+2)(n+3) 4 for every 4. Use induction to prove 2n is O(n!). I.e, choose witnesses C and k and show that for all n > k, 2n 6 Cn!. 5. Use induction to prove that 6|(n3 n) for any nonnegative integer n. 6. Let fn denote the nth Fibonacci number. Prove that f12 + f22 + . . . + fn2 = fn fn+1 for all positive integers n. 7. Let fn denote the nth Fibonacci number. Prove that fn+1 fn1 fn2 = (1)n for all positive integers n. 8. Give a recursive definition of the functions max and min, where max(a1 , a2 , . . . , an ) evaluates to the maximum of numbers a1 , a2 , . . . , an , n > 1, and min(a1 , a2 , . . . , an ) evaluates to the minimum of the numbers. 9. Give a recursive definition for the set S consisting of finite bit-strings containing an even number of 0s, and all 0s (if present) appear before all 1s. That is, 001 S and 1 S, but 01111 / S, and 01100011 / S. 10. Give a recursive definition for the set of palindromes over the alphabet {1, 0}. Bonus Question - 10 points Use induction to prove that for any finite bitstring s, if s ends in a 1, then 01 occurs at most one more time than 10. Induct on the length of s