Wednesday 15/9 - EXERCISES W3 - Invariants and Induction - ANSWERS

Preparation

Lecture: Monday,Thursday,Friday, week 2. Monday, week 3.

Read: Lehman, Leighton, and Meyer: Chapter 5 and 6 (6.1-6.2).

Exercises from the Book

Make sure you are comfortable with the following before you start the next exercises:

Chapter 5: Problems 5.16 (induction step +2), 5.22 (bogus proof about Fibonacci), 5.23 (step +3).
Chapter 6: Problems 6.3 (Wall-E and Eve), 6.14(b) (red/blue balls)

Exercises

(1.) Is n³ ≤ n², for all n ≥ 0? What happens when you try to prove it by induction?

(2.) Show that 8ⁿ - 3ⁿ is divisible by 5, for all n ≥ 1.

(3.) Show that 1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3, for all n ≥ 1.

(4.) Show that 4n < 2ⁿ, for all n ≥ 5.

(5.) Show that the n-th derivative of xⁿ is n!, for all n ≥ 1. (You can compute the n-th derivative by taking the derivative n times.)

(6.) Take a look at the following recursive function definition for \(f : \mathbb{N}^+ \times \mathbb{N} \rightarrow \mathbb{N}\): \[ f(x,n) = \begin{cases} 1 & \; \text{if} \; n=0 \\ f(x,n/2)^2 & \; \text{if} \; n>0 \; \text{and} \; n \; \text{is even} \\ x \cdot f(x,n-1) & \; \text{if} \; n \; \text{is odd} \end{cases} \] Prove that \(f(x,n) = x^n\) for all \(x>0\) and all \(n \geq 0\).

(7.) A chocolate bar consists of a number of squares (say, n > 0) arranged in a rectangular pattern. You can split the bar into two smaller bars only by breaking along the lines between the squares. You can repeat this process as many times as you want. What is the minimum number of breaks you have to perform to break the chocolate bar completely into n small squares?

Prove your claim by induction.

(8.) Imagine that you live in a country that only has two kinds of stamps: stamps that cost 4kr and stamps that cost 5kr. Sending a letter may cost any amount from 12kr upwards.

Show that you can always use 4kr and/or 5kr stamps to get to any amount ≥ 12kr you have to pay for a letter.

Examples: 12kr can be made by 3 stamps of 4kr. 13kr can be made by 2 stamps of 4kr and one stamp of 5kr. 14kr can be made by 2 stamps of 5kr and one of 4kr, etc.

(9.) You are given a non-empty list of natural numbers. You repeat the following steps:

If the list only has one number, you stop.
If the list has more than one number, remove the least number. (If there are several least numbers, remove one of them.)

What can you say about the last number that is left, compared to the list of numbers you started with?

Prove by using an invariant that you are right.

(10.) We are given two natural numbers A and B, either both odd or both even. We write them down on a piece of paper. Now, we repeat the following steps:

Look at the paper. If the distance between the two numbers on the paper is 0 or 1, we stop.
If the distance between the two numbers on the paper is greater than 1, we cross out the smallest number, add 1 to it, and write the result down on the paper. We also cross out the largest number, subtract 1 from it, and write the result down on the paper.

What can you say about the numbers on the paper when we stop? What can you say about the relationship between A and B and the numbers on the paper when we stop?

Prove by using an invariant that you are right.

Starred Exercises

These exercises are for students who are looking for a challenge.

(1*.) Look at the definition of the Haskell function ++. Show that for any lists xs, ys, and zs, the following holds:

xs ++ (ys ++ zs) = (xs ++ ys) ++ zs

In other words, show that ++ is associative!

Hint: Prove the following: For any natural number n, if we have a list xs of length n, and two other lists ys and zs, then xs ++ (ys ++ zs) = (xs ++ ys) ++ zs. Do this by induction over n.

(2*.) Problem 6.8 from the book: The 15-puzzle.

(3*.) Take a look at the following shape of a puzzle piece:

Now, imagine a grid of 1024x1024 squares, of which we remove 1 square. Show that the rest of the grid can be completely covered by pieces of the shape above (without any piece sticking out on the side, or covering the square we removed).

(Hint: Prove that you can do this for any grid of dimensions 2ⁿ x 2ⁿ, by induction over n.)