CS 70 Fall 2016
Discrete Mathematics and Probability Theory Seshia and Walrand
HW 2
1. Sundry Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of hw party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade. 2. (5 points) Prove that 13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2 for all integers n > 0. Solution: We will do an induction on n: • Proposition: P(n) = “13 + · · · + n3 = (1 + · · · + n)2 ”. • Base case: P(1) is the proposition 13 = (1)2 , which is true, since 1 = 1. • Inductive step: prove P(n) =⇒ P(n + 1) for all n > 0. (a) The inductive hypothesis is 13 + · · · + n3 = (1 + · · · + n)2 , where n > 0. (b) To prove: 13 + · · · + n3 + (n + 1)3 = (1 + · · · + n + (n + 1))2 . (c) Taking the expression on the right hand side, we get ((1 + · · · + n) + (n + 1))2 = (1 + · · · + n)2 + 2(1 + · · · + n)(n + 1) + (n + 1)2 (since (x + y)2 = x2 + 2xy + y2 for all x, y) = (13 + · · · + n3 ) + 2(1 + · · · + n)(n + 1) + (n + 1)2 (using the inductive hypothesis) n(n + 1) = (13 + · · · + n3 ) + 2 (n + 1) + (n + 1)2 2 (since 1 + · · · + n = n(n + 1)/2 for all n) = 13 + · · · + n3 + (n + 1)3
(simplifying the right-hand side)
3. (10 points) A Tricky Game (a) (10 points) CS 70 course staff invite you to play a game: Suppose there are n2 coins in a n × n grid (n > 0), each with their heads side up. In each move, you can pick one of the n rows or columns and flip over all of the coins in that row or column. However, you are not allowed to re-arrange them in any other way. You have an unlimited number of moves. If you happen to reach a configuration where there is exactly one coin with its tails side up, you will get an extra credit. Are you able to win this game? Does that apply to all n? Prove your answer.
CS 70, Fall 2016, HW 2
1