Here are some answers for the exercises.

1. No, take for example n=2. If you prove this by induction, the base case (n=0) goes through, but you get stuck in the step case. Assuming that k³ ≤ k² for some k is not enough to prove (k+1)³ ≤ (k+1)².

2. To prove: 8ⁿ - 3ⁿ is divisable by 5, for all n ≥ 1.

Proof: By induction over n.

Base case: n=1. 8¹ - 3¹ = 5, which is divisable by 5.

Step case: n=k+1.

1. By the induction hypothesis (IH), we know that 8^k - 3^k is divisable by 5.

2. Now look at:
       8^k+1 - 3^k+1
    = 8⋅8^k - 3⋅3^k
    = (5+3)⋅8^k - 3⋅3^k
    = 5⋅8^k + 3⋅8^k - 3⋅3^k
    = 5⋅8^k + 3⋅(8^k - 3^k)
This is divisable by 5, because it is the sum of 5⋅8^k, which is divisable by 5 and 3⋅(8^k - 3^k), which is divisable by 5 according to the IH.

3. To prove: 1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3, for all n ≥ 1.

Proof: By induction over n.

Base case: n=1. 1⋅2 = 1⋅2⋅3/3. OK!

Step case: n=k+1.

1. By the induction hypothesis (IH), we know that 1⋅2 + 2⋅3 + 3⋅4 + ... + k(k+1) = k(k+1)(k+2)/3.

2. Now look at:
       1⋅2 + 2⋅3 + 3⋅4 + ... + k(k+1) + (k+1)(k+2)
    = k(k+1)(k+2)/3 + (k+1)(k+2)     (because of IH)
    = k(k+1)(k+2)/3 + 3(k+1)(k+2)/3
    = (k(k+1)(k+2) + 3(k+1)(k+2))/3
    = (k+1)(k+2)(k+3)/3
Which is what we had to prove!

4. To prove: 4n < 2ⁿ, for all n ≥ 5.

Proof: By induction over n.

Base case: n=5. 4⋅5 = 20 < 32 = 2⁵. OK!

Step case: n=k+1. We know that k ≥ 5.

1. By the induction hypothesis (IH), we know that 4k < 2^k.

2. Now look at:

       4(k+1)

    = 4k + 4

    < 2^k + 4     (because of IH)

    < 2^k + 2^k     (because k > 2)

    = 2⋅2^k

    = 2^k+1

Which is what we had to prove!

5. To prove: The n-th derivative of xⁿ is n!, for all n ≥ 1.

Proof: By induction over n.

Base case: n=1. The derivative of x¹ is 1, which equals 1!. OK!

Step case: n=k+1.

1. By the induction hypothesis (IH), we know that the k-th derivative of x^k is k!.

2. Now look at:

       the (k+1)-th derivative of x^k+1

    = the k-th derivative of [ (k+1)x^k ]

    = (k+1) ⋅ [ the k-th derivative of x^k ]

    = (k+1) ⋅ k!     (because of IH)

    = (k+1)!

Which is what we had to prove!

6. To prove: f(x,n) = xⁿ for all x>0 and all n≥0.

Proof: By strong induction over n.

Base case: n=0. f(x,0) = 1 = x⁰. OK!

Step case: n>0.

1. By the induction hypothesis (IH), we know that for all 0 ≤ k < n, we have that f(x,k) = x^k.

2. Now we do a case split.

Case 1: n is even.

Now look at:

       f(x,n)

    = f(x,n/2)²

    = (x^n/2)²     (because of IH, n/2 < n)

    = xⁿ, which is what we had to prove!

Case 2: n is odd.

Now look at:

       f(x,n)

    = x ⋅ f(x,n-1)

    = x ⋅ (x^n-1)     (because of IH, n-1 < n)

    = xⁿ, which is what we had to prove!

What we had to prove held in both cases, and therefore it always holds.

7. The number of breaks is always n-1, regardless of how you break.

To prove: To break a bar of chocolate with n squares into squares only, we need n-1 breaks, for any n ≥ 1.

Proof: By strong induction over n.

Base case: n=1. If we already have one square only, we don't need to break anything, so 0 breaks. OK!

Step case: n>1.

1. By the induction hypothesis (IH), we know that for all 1 ≤ k < n, to break any bar of chocolate into k squares, we need k-1 breaks.

2. Since we have more than one square (n>1), we need to do at least one break. This leaves us with two new chocolate bars, of sizes k1 and k2, respectively. Here, k1+k2=n. We know that 1 ≤ k1 < n and also 1 ≤ k2 < n. By using the IH twice, we know that to break each of these into squares would require k1-1 breaks and k2-1 breaks, respectively. So, the total number of breaks is 1 + (k1-1) + (k2-1) = k1+k2 - 1 = n - 1. (No matter how we make the first break.)

Which is what we had to prove!

8. To prove: We can get to any amount n by summing up an appropriate number of 4's and 5's, for n ≥ 12.

Proof: By strong induction over n.

Base cases: n=12: 4+4+4=12. n=13: 4+4+5=13. n=14: 4+5+5=14. n=15: 5+5+5=15.

Step case: n>15.

1. By the induction hypothesis (IH), we know that for all 12 ≤ k < n, we can find the appropriate number a of 4's and b of 5's such that k = 4a + 5b.

2. Let a and b be the appropriate number of 4's and 5's to get the amount n-4. So, we have that n-4 = 4a + 5b. (We know these exist because of the IH, and 12 ≤ n-4 < n.)

3. The number of 4's and 5's to get the amount n is (a+1) and b, respectively, because n = 4(a+1) + 5b.

Which is what we had to prove!

9. Let M be the maximum number in the original list.

The invariant we are looking for is "M is an element of the list".

Obviously, the invariant holds in the beginning.

If the invariant holds for a list (so M is an element of that list), and we remove the smallest number from that list, we have not removed M, so the invariant still holds.

In other words, the invariant should hold for any of the lists we encounter, including the last one, when only one number is left. This last number must be M, the maximum element from the original list.

10. One invariant I1 we have is: the numbers on the paper are either both odd, or both even.

Obviously, it holds at the beginning. Also, if we have a piece of paper with two even numbers or two odd numbers, and we add 1 and subtract 1, we still have two even numbers or two odd numbers.

So, at the end, they must both be odd or both be even. In other words, their distance cannot be 1, so it must be 0, which means that at the end, the numbers are equal.

Another invariant I2 we have is: the sum of the numbers on the paper equals A+B.

Obviously, it holds at the beginning. Also, if we have a piece of paper with two numbers whose sum equals A+B, then after adding 1 and subtracting 1, the sum is still A+B.

So, at the end, the sum must still equal A+B.

Combining both invariants, at the end we have a number X that appears twice on the paper (from I1). From I2, we know that X+X = A+B, in other words that X is the average of A and B.