Homework 2 (assigned June 29, due July 5)

Reading: Rosen chapter 4, sections 4.1–4.2.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Formulate and prove by mathematical induction a rule for the sums 1², 2² − 1², 3² − 2² + 1², 4² − 3² + 2² − 1², 5² − 4² + 3² − 2² + 1², etc.

2. Prove by induction that n³ + (n + 1)³ + (n + 2)³ is divisible by 9 for all positive integers n.

3. Prove by induction that if h > −1, then 1 + nh ≤ (1 + h)ⁿ for all nonnegative integers n. This is called Bernoulli's inequality.

4. Prove by induction that the following laws for positive exponents are valid, where n and m are positive integers and a and b are real numbers.
   1. (a^m)ⁿ = a^mn.
   2. (ab)ⁿ = aⁿbⁿ.

5. A jigsaw puzzle is put together by successively joining pieces that fit together into blocks. A move is made each time a piece is added to a block, or when two blocks are joined. Use strong induction to prove that no matter how the moves are carried out, exactly n − 1 moves are required to assemble a puzzle with n pieces.

6. This problem considers exact L-tilings of a checkerboard. See Rosen, section 4.1, example 13, for definitions and terminology regarding tilings.
   1. Show that a 5 × 5 checkerboard with a 1 × 1 corner square removed has an exact L-tiling.
   2. Find a 5 × 5 checkerboard with a 1 × 1 square removed that does not have an exact L-tiling. Prove that an exact L-tiling does not exist for this board.

7. Starting with 0, two players alternately add 1, 2, or 3 to a single running total. The player who first brings the total to at least 1000 wins. Prove that the second player has a strategy to win against any strategy for the first player. Hint: Use induction to prove a more general statement.

8. What is the flaw in the following proof?
   Theorem. Let a be any positive number. For all positive integers n we have a^{n − 1} = 1.
   Proof. By induction on n.
   Base case: If n = 1, a^{n − 1} = a^{1 − 1} = a⁰ = 1.
   Inductive step: By induction, assuming that the theorem is true for 1, 2, …, n, we have
   a^{(n+1) − 1} = aⁿ = a^{n − 1} × a^{n − 1}/a^{n − 2} = 1 × 1 / 1 = 1.
   Therefore, the theorem is true for n + 1 as well.

Assigned problems (to be handed in):

1. Prove by induction the following summation formula:
   1³ + 2³ + … + n³ = (1 + 2 + … + n)². (5 points)
2. Prove by induction that if n ≥ 10, then 2ⁿ > n³. (10 points)

3. Use strong induction to prove that every positive integer n can be written as a sum of distinct powers of 2, i.e., as a sum of a subset of the integers 2⁰ = 1, 2¹ = 2, 2² = 4, etc. (5 points)

4. The following proof by induction seems correct, but for some reason the equation for n = 6 gives 1/2 + 1/6 + 1/12 + 1/20 + 1/30 = 5/6 on the left-hand side, and 3/2 − 1/6 = 4/3 on the right-hand side. Find the mistake. (10 points)
   Theorem. For all positive integers n,
   1/(1 × 2) + 1/(2 × 3) + … + 1/((n − 1) × n) = 3/2 − 1/n.
   Proof. By induction on n.
   Base case: For n = 1, 3/2 − 1/n = 1/(1 × 2).
   Inductive step: Assuming that the theorem is true for n,
   1/(1 × 2) + … + 1/((n − 1) × n) + 1/(n × (n + 1)) = 3/2 − 1/n + 1/(n × (n + 1))
                                                                                = 3/2 − 1/n + [1/n − 1/(n + 1)]
                                                                                = 3/2 − 1/(n + 1).
   
   Therefore, the theorem is true for n + 1 as well.

5. A tiling is a complete and exact covering of a region (usually planar) with multiple copies of some smaller shape. Suppose we are given L-shaped tiles, i.e., a 2 × 2 square tile with a missing 1 × 1 square. Prove that every region R of size (2i) × (3j), where i and j are positive integers, with no square missing has an exact L-tiling. (10 points)

6. Recall the definition of a line map given in class:
   Define a line map as follows:

   1. A blank rectangle is a line map.
   2. A line map with a straight line drawn all the way across it is a new line map.
   1. Prove by induction on the number of lines that a line map with n distinct lines has at least n + 1 regions. (5 points)
   2. Prove by induction on the number of lines that a line map with n distinct lines has at most 2ⁿ regions. (5 points)
   3. Part (1) gives a lower bound on the number of regions in a line map. For example, a line map with 5 lines must have at least 6 regions. Give an example of a line map that achieves this lower bound, i.e., draw a line map with 5 lines and 6 regions. (5 points)
   4. Part (2) says that a line map with 3 lines can have at most 8 regions. Can you draw a line map with 3 lines that achieves this upper bound? Do so, or explain why you cannot. (5 points)

7. In this problem H_n denotes the nth harmonic number. Modify the argument given in class proving H_2^m ≥ 1 + m/2 (cf. Rosen, section 4.1, example 7) to prove that H_2^m ≤ 1 + m for all m > 0. (10 points)