Homework Assignment 1

Due: by 10am on Thu 31 Jan
Worth: 8%

For each question, please write your answer formally following the detailed format given in lecture (in particular, define P(n) carefully in your inductive proofs). Keep in mind that approximately half of the marks for each question will be given purely for having the correct proof structure, written up clearly and precisely, irrespective of the correctness of the proof. Also, make sure that you use notation and terminology correctly, and that you explain and justify what you are doing — marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. For each statement below, give two different inductive proof structures that could be used to prove the statement. Fill in as much of each proof structure as you possibly can without knowing more about P(n).

    1. For all odd integers n ≥ 3, P(n).
    2. For all n that are positive multiples of 3, P(n).
    3. For all n that are powers of 2 (i.e., n = 2k for some k ∈ N), P(n).

    For example, the statement "∀n ≥ 12, P(n)" can be proved using any of the proof structures below (for this example, I'm giving more than two possibilities, but in your answers, you only need to give two).

    • Predicate: Let Q(n) = "n ≥ 12 → P(n)" and prove ∀n, Q(n) by simple induction.
      Base Case: Q(0) is the statement "0 ≥ 12 → P(0)", which is vacuously true (since 0 < 12).
      Ind. Hyp.: Let n ∈ N and suppose Q(n), i.e., n ≥ 12 → P(n).
      Ind. Step: To prove Q(n+1), suppose n+1 ≥ 12 and consider two cases:
      • Case 1: If n+1 = 12, then prove P(12) [= P(n+1)] directly.
      • Case 2: If n+1 > 12, then n ≥ 12 so by the IH, we know P(n) holds. Use this to prove P(n+1).
      In either case, P(n+1) holds, so Q(n+1) holds as well.
      Conclusion: By induction, ∀n ∈ N, Q(n), i.e., ∀n ≥ 12, P(n).
    • Predicate: Let Q(n) = P(n+12) and prove ∀n, Q(n) by simple induction.
      Base Case: Prove Q(0) = P(12) directly.
      Ind. Hyp.: Let n ∈ N and suppose Q(n) = P(n+12).
      Ind. Step: Prove Q(n+1) = P(n+13).
      Conclusion: By induction, ∀n ∈ N, Q(n), i.e., ∀n ≥ 12, P(n).
    • Predicate: P(n).
      Base Case: Prove P(12) directly.
      Ind. Hyp.: Let n ≥ 12 and suppose P(n).
      Ind. Step: Prove P(n+1).
      Conclusion: By induction, ∀n ≥ 12, P(n).

  2. Consider the following solitaire game, played with 2k coins, for some k ∈ N, and some target natural number n ≤ 2k.

    • Divide the coins into two piles: initially, place all 2k coins in one pile, and 0 coins in the other pile — we represent this as a pair (2k,0).
    • The goal is to succeed in making one pile contain exactly n coins (either pile will do), i.e., we want to end up with either (n,2k-n) or (2k-n,n).
    • There is only one way to move coins from one pile to the other: select one pile, split it in half, and move half of the coins to the other pile. This means that there are two possible results starting from an arbitrary position (a,b): (a/2,b+a/2) or (a+b/2,b/2).
      Obviously, a move can be carried out only if each pile contains an even number of coins, which means that the game is over if the piles ever end up with an odd number of coins.
    • For example, if we start with 64 coins and n = 27, there is a winning sequence of moves: (64,0) ⇒ (32,32) ⇒ (48,16) ⇒ (24,40) ⇒ (44,20) ⇒ (54,10) ⇒ (27,37).

    For what values of k and n is it possible to solve this game? Make a conjecture, state it precisely, and prove it formally.

  3. Read Examples 1.9 (pp.34–35), 1.10 (pp.35–37), and 1.13 (pp.41–42) in the course textbook, as well as the introductory material on pp.32–34.
    Then, prove that for all n ≥ 1, every full binary tree with n nodes contains exactly (n + 1) / 2 leaves.