Homework_5

EECS 203: Discrete Mathematics Winter 2024 Homework 5 Due Thursday, Mar. 7th , 10:00 pm No late homework accepted past midnight. Number of Problems: 7 + 2 Total Points: 100 + 30 • Match your pages! Your submission time is when you upload the file, so the time you take to match pages doesn’t count against you. • Submit this assignment (and any regrade requests later) on Gradescope. • Justify your answers and show your work (unless a question says otherwise). • By submitting this homework, you agree that you are in compliance with the Engi- neering Honor Code and the Course Policies for 203, and that you are submitting your own work. • Check the syllabus for full details. 1

Individual Portion 1. Easy as 3, 18, 93 [16 points] Let P ( n ) be the statement that 3 + 3 · 5 + 3 · 5 2 + ... + 3 · 5 n = 3(5 n +1 − 1) 4 . In this problem, we will prove using weak induction that P ( n ) is true whenever n is a non-negative integer. (a) What is the statement P (0)? Complete the base case by showing that P (0) is true. (b) In the base case we prove P (0); what do you need to prove in the inductive step? (c) What is the inductive hypothesis for your proof? (d) Complete the inductive step, indicating where you used the inductive hypothesis. Reminder: You should prove this equation using a chain of equalities, starting on one side and transforming it into the other side. You should not start with the equation you want to prove and transform both sides to be equal. (e) Explain why this proof shows P ( n ) is true for all non-negative integers n . Solution: (a) Base Case: P (0) : 3 = 3(5 0+1 ) − 1) 4 3 = 3 so the Base Case holds (b) We need to prove that since the base case is true, P ( n ) is true for all non-negative integers. We must allow k to be an arbitrary integer ≥ 0 (c) Assuming P ( k ) : 3 + 3 · 5 + 3 · 5 2 + ... + 3 · 5 k = 3(5 k +1 − 1) 4 We want to show P ( k + 1) : 3 + 3 · 5 + 3 · 5 2 + ... + 3 · 5 k +1 = 3(5 k +1+1 − 1) 4 (d) (3 + 3 · 5 + 3 · 5 2 + ... + 3 · 5 k ) + 3 · 5 k +1 = 3(5 k +2 − 1) 4 3(5 k +1 − 1) 4 + 3 · 5 k +1 = 3(5 k +2 − 1) 4 3 · 5 k +1 − 3 4 + 3 · 5 k +1 = 3(5 k +2 − 1) 4 3 · 5 k +1 − 3+12 · 5 k +1 4 = 3(5 k +2 − 1) 4 3(5 k +1 +4 · 5 k +1 ) − 3 4 = 3(5 k +2 − 1) 4 3(5 k +2 − 1) 4 = 3(5 k +2 − 1) 4 (e) This proof shows that P ( n ) is true for all non-negative integers because by rules of induction, if the base case is true and P ( k + 1) is true, we know that each following number must be true 2

(a) Base Case P (1) : 5 | 3 4 + 4 → 5 | 85 since 85 is divisible by 5, P (1) holds (b) Inductive step : Consider an arbitrary integer k with k ≥ 1 Assume P ( k ) : 3 4 k + 4 = 5 m Want to show P ( k + 1) : 3 4( k +1) + 4 = 5 p (c) Working with LHS P ( k + 1) : 3 4( k +1) + 4 = 3 4 k +4 + 4 3 4 (3 4 k + 4) + 85 3 4 (5 m ) + 85 5(3 4 + 17) 5 p since p = 5(3 4 + 17) Arriving at the RHS of P ( k + 1), we have completed the inductive hypothesis This means P ( n ) holds true for all n ≥ 1 4. Please Pretend Postage Pun Present [12 points] Let P ( n ) be the predicate “ n cents can be formed using 3 and 7 cent stamps.” (a) Find the smallest c ∈ N so that ∀ n ≥ c, P ( n ). (b) Prove by induction that ∀ n ≥ c, P ( n ). Use the minimum number of base cases needed. Solution: (a) The smallest c = 12. By the chicken nugget theorem (3 ∗ 7) − 3 − 7 = 11, so the smallest c must then be 12, which can be made by four 3 cent stamps. (b) Base cases P (12) = 3 + 3 + 3 + 3 P (13) = 3 + 3 + 7 P (14) = 7 + 7 Let k be an integer with k ≥ 15 Assume P ( j ) is true for all 12 ≤ j ≤ k − 1 P ( k − 3) is true by inductive hypothesis (because 12 ≤ k − 3 ≤ k − 1) To make k cents: first make k − 3 cents, then add an additional 3 cent stamp Therefore P ( k ) is true. 4

5. Inductive Delights [14 points] Assume that a chocolate bar consists of n ≥ 1 squares arranged in a rectangular pattern. Any rectangular piece of the bar including the entire bar can be broken along a vertical or a horizontal line separating the squares. Assuming you can only break the bar along one axis at a time, determine how many breaks you must successively make to break the bar into n separate squares. Use strong induction to prove your answer. Solution: Allow B ( n ) to denote the number of breaks needed to break a chocolate bar of n ≥ 1 squares into n pieces. (a) Base Cases : B (1) = 0 meaning 0 breaks are needed to maintain a 1 square of chocolate. B (2) = 1 meaning 1 break is needed to separate a chocolate made up of two squares B (3) = 2 meaning 2 breaks are needed to break up a 3 square chocolate (b) Inductive Step : For bars with n + 1 pieces, any break will split the piece into two halves, giving us two pieces, one with 1 ≤ k < n + 1 pieces and the other with n + 1 − k pieces. So we have: B ( n + 1) = B ( k ) + B ( n + 1 − k ) + 1 By strong induction, we know that since k and n + 1 − k are less than one, the formula holds So we have: c ( n + 1) = c ( k ) + c ( n + 1 − k ) + 1 ( k − 1) + ( n + 1 − k − 1) + 1 = n This means that the formula holds for c ( n + 1), meaning the inductive conclusion holds for any choice n 6. A Mess of Messages [12 points] We are sending messages made up of the characters “a”, “b”, and “c”. An “a” takes 1 microsecond to send, and a “b” or “c” takes 2 microseconds to send. Let M ( n ) denote the number of distinct messages we can send using exactly n microseconds (in particular, the message cannot be sent in fewer than n microseconds), for n ≥ 0. (a) Give a recurrence relation for M ( n ) . 5

Finally, in order to fulfill the sink requirement and ignoring the last day, L ( n − 2) + L ( n − 2) + L ( n − 3) (b) According to the recurrence relation, the minimum necessary conditions needed to specify L ( n ) is 3. This is because of L ( n − 3), meaning there are are three minimum ”ways” for Carrot to sleep ( L 0 , L 1 , L 2 ) 7