2. (Induction.) (a) Consider the following two-player game: starting with the single number 123, two players alternately subtract numbers from the set {1, 2, 3} from this value. The player who first gets this sum to 0 wins. If you want to win this game, should you go first or second? Prove that your chosen player has a winning strategy.

(b) Recall from class that the Fibonacci numbers were defined as follows: f0 = 0, f1 = 1 and for all n 1, fn+1 = fn + fn1. i. For any natural number n 3, show that the quotient of fn+1 fn is 1 and the remainder of fn+1 fn is fn1. ii. Prove (by induction/recursion, if you like) that the Euclidean Algorithm takes n 2 loops to calculate gcd(fn, fn1), for any integer n 3.

(c) Take an equilateral triangle with side length 2n . Divide it up into side-length 1 equilateral triangles, and delete the top triangle. Call this shape Tn: Take three side-length 1 equilateral triangles. Join them together to form the following tile: Prove that you can tile1 Tn with tiles, for every n N.