CSE 20 Spring 2021 Homework 5 Due date: Wednesday, May 12, 2021 at 11:59pm Topics Induction Reading Rosen Sections 5

CSE 20 Spring 2021 Homework 5 Due date: Wednesday, May 12, 2021 at 11:59pm Topics Induction Reading Rosen Sections 5.1, 5.2. Key Concepts induction: Regular induction, strong induction. 1. (8 points) Consider the statement: For all integers n ≥ 0, n is even. Find the flaw in the following proof: ( identify the line by number and explain why it is incorrect.) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Basis Step: The statement is true for 0 since 0 is even (0 = 2 ∗ 0) Let k be an arbitrary integer such that k ≥ 0. Assume that for all integers m such that 0 ≤ m ≤ k that m is even. (We want to show that k + 1 is even.) Write k + 1 = a + b such that a and b are both non-negative integers less than k + 1. Then by the inductive hypothesis, a and b are both even. This means that there exist integers x and y such that a = 2x and b = 2y. Therefore k + 1 = a + b = 2x + 2y = 2(x + y) Since x + y is an integer, then k + 1 is even (as required). Therefore, by induction, all integers greater than or equal to 0 are even. 2. (9 points) Suppose you only have 4 cent coins and 7 cent coins, Fill in the blanks of the following strong induction proof that you can make change for any integer amount n ≥ 18. Solution: By strong induction on n. Basis step: Show that it is true for each number: • • • • n = 18 : n = 19 : n = 20 : n = 21 : (1) (2) (3) (4) Inductive step: Let k be an arbitrary integer with k ≥ (5) and assume that, for all m with (6) ≤ m < k, we can make change for m cents. WTS: we can make change for k cents. Since (7) ≤ k−4 < k, by the Inductive Hypothesis (8) (explain your conclusion). Therefore we can make change for k cents using 4 cent coins and 7 cent coins by (9) 3. (10 points) (a) Find an appropriate integer value for X that makes the statement true: For all integers n ≥ X, 4n < n!. (b) Prove the statement (with your value of X from the previous part.) 1 . 4. (8 points) The tribonacci numbers are defined in the following way: t0 = 1, t1 = 1, t2 = 1, tn = tn−1 + tn−2 + tn−3 for all n ≥ 3 Prove that tn ≤ 2n for all n ≥ 0. 5. Consider the game “25” played with two players; player 1 and player 2. The game starts with 25 jellybeans in a pile. Each turn consists of the active player taking 1, 2 or 3 jellybeans, then passing the turn. Player 1 takes the first turn. The person who takes the last jellybean loses. Example: The numbers in the table below are bolded to indicate the player who is taking a turn. Beans in Jar 25 22 19 17 15 13 10 9 8 6 5 2 1 0 Player 1 Beans 0 3 3 5 5 7 7 8 8 10 10 13 13 14 Player 2 Beans 0 0 3 3 5 5 8 8 9 9 10 10 11 11 Because player 1 takes the last bean from the jar on the last turn, player 2 wins. Prove that Player 2 has a winning strategy. (a) ( 4 points) Describe the winning strategy of Player 2. (b) (8 points) Prove by induction that the strategy will win every time.