The idea is that you should prepare these exercises at home, by yourself or with your group. If you have any questions, you can come to the exercise session and ask them to the assistants. (If you do not prepare in advance, there is little point in coming!)

Lectures: Monday+Thursday+Friday, week 2; Monday, week 3.

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

Some answers are available.

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

Chapter 5: Problems 5.16, 5.21, 5.22, 5.23.

Chapter 6: Problems 6.1, 6.2

Now, please think about these.

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 : ℕ⁺ x ℕ -> ℕ:

f(x,0) = 1
f(x,n) = f(x,n/2)²   ,   if n > 0 and n is even
f(x,n) = x⋅f(x,n-1)   ,   if n is odd

Prove that f(x,n) = xⁿ for all x>0 and all n≥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.)

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.

Prove by using an invariant that you are right.

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

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

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

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*. Given a bag that contains 50 white balls and 50 black balls. You repeat the following procedure until only one ball is left in the bag:

You take out 2 balls: if they have the same color, you put back a black ball in the bag; if they have different colors, you put back a white ball in the bag. (You may need extra black balls to do this.)

What can you say about the color of the last ball in the bag?

Hint: find an invariant that says something about the relationship between the number of black balls and the number of white balls.

3*. Problem 6.8 from the book: The 15-puzzle.

(This exercise appears in the book in section 5.1.5. I leave it here for completeness.

4*. 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.)