Exercises Week 3 - Invariants and Induction - Answers
(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 k3 ≤ k2 for some k is not enough to prove (k+1)3 ≤ (k+1)2.
(2.) To prove: 8n - 3n is divisable by 5, for all n ≥ 1.
Proof: By induction.
Let P(n) = "8n - 3n is divisable by 5".
Base case: P(1): 81 - 31 = 5, which is divisable by 5.
Step case: P(k) => P(k+1), for k≥1.
Assume: P(k) = "8k - 3k is divisable by 5" (IH), and k≥1.
Show: P(k+1) = "8k+1 - 3k+1 is divisable by 5".
Now look at:
8k+1 - 3k+1
= 8⋅8k - 3⋅3k
= (5+3)⋅8k - 3⋅3k
= 5⋅8k + 3⋅8k - 3⋅3k
= 5⋅8k + 3⋅(8k - 3k)
This is divisable by 5, because it is the sum of 5⋅8k (which is divisable by 5) and 3⋅(8k - 3k) (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.
Let P(n) = "1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3".
Base case: P(1). 1⋅2 = 1⋅2⋅3/3. OK!
Step case: P(k) => P(k+1), for k≥1.
Assume: P(k) = "1⋅2 + 2⋅3 + 3⋅4 + ... + k⋅(k+1) = k(k+1)(k+2)/3" (IH), and k≥ 1.
Show: P(k+1) = "1⋅2 + 2⋅3 + 3⋅4 + ... + k⋅(k+1) + (k+1)⋅(k+2) = (k+1)(k+2)(k+3)/3".
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 < 2n, for all n ≥ 5.
Proof: By induction.
Let P(n) = "4n < 2n".
Base case: P(5): 4⋅5 = 20 < 32 = 25. OK!
Step case: P(k) => P(k+1), for n≥5.
Assume: P(k) = "4k < 2k" (IH), and k≥5.
Show: P(k+1) = "4(k+1) < 2k+1".
Look at:
4(k+1)
= 4k + 4
< 2k + 4 (because of IH)
< 2k + 2k (because k > 2)
= 2⋅2k
= 2k+1
Which is what we had to prove!
(5.) To prove: The n-th derivative of xn is n!, for all n ≥ 1.
Proof: By induction.
Let P(n) = "the n-th derivative of xn is n!".
Base case: P(1). The (1st) derivative of x1 is 1, which equals 1!. OK!
Step case: P(k) => P(k+1), for k≥1.
Assume: P(k) = "the k-th derivative of xk is k!" (IH), and k≥1.
Show: P(k+1) = "the (k+1)-th derivative of xk+1 is (k+1)!".
Look at:
the (k+1)-th derivative of xk+1
= the k-th derivative of [ (k+1)xk ]
= (k+1) ⋅ [ the k-th derivative of xk ]
= (k+1) ⋅ k! (because of IH)
= (k+1)!
Which is what we had to prove!
(6.) To prove: f(x,n) = xn for all x>0 and all n≥0.
Proof: By strong induction.
Let P(n) = "f(x,n) = xn, for all x>0".
Base case: P(0): f(x,0) = 1 = x0. OK!
Step case: (P(0) /\ ... /\ P(k)) => P(k+1), for k≥0.
Assume: for 0≤i≤k: P(i) = "f(x,i) = xi, for all x>0" (IH), and k≥0.
Show: P(k+1) = "f(x,k+1) = xk+1, for all x>0"
Now we do a case split.
Case 1: (k+1) is even.
Now look at:
f(x,k+1)
= f(x,(k+1)/2)2
= (x(k+1)/2)2 (because of IH, i=(k+1)/2 ≤ k)
= xk+1, which is what we had to prove!
Case 2: (k+1) is odd.
Now look at:
f(x,k+1)
= x ⋅ f(x,k+1-1)
= x ⋅ f(x,k)
= x ⋅ (xk) (because of IH, i=k)
= xk+1, 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.
Let P(n) = "to break a bar of chocolate with n squares into squares only, we need n-1 breaks".
Base case: P(1). If we already have one square only, we don't need to break anything, so 0 breaks. OK!
Step case: (P(1) /\ ... /\ P(k)) => P(k+1), for k≥1.
Assume: for 1≤i≤k: P(i) = "to break a bar of chocolate with i squares into squares only, we need i-1 breaks" (IH), and k≥1.
Show: P(k+1) = "to break a bar of chocolate with k+1 squares into squares only, we need k breaks"
Since we have more than one square (k+1>1), we need to do at least one break. This leaves us with two new chocolate bars, one with k1 and one with k2 squares, respectively. The total number of squares does not change, so k1+k2=k+1. We know that 1 ≤ k1 ≤ k and also 1 ≤ k2 ≤ k.
By using the IH twice (on k1 and k2), 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 = (k+1) - 1 = k.
(This holds no matter how we make the first break.)
Which is what we had to prove!
An alternative answer, which does not really use a proof by induction, goes like this. In the beginning, we have 1 block of chocolate on the table. At the end, we have n small pieces.
Everytime we make a break, we replace 1 block of chocolate with 2 smaller ones. The number of distinct blocks on the table thus increases by 1 every time we make a break.
To go from 1 to n, we thus need n-1 breaks.
(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 (special*) induction.
Let P(n) = "we can get amount n by summing up an appropriate number of 4's and 5's".
Base cases: P(12): 4+4+4=12. P(13): 4+4+5=13. P(14): 4+5+5=14. P(15): 5+5+5=15.
Step case: P(k) => P(k+4), for k≥12.
Assume: P(k) = "we can get amount k by summing up an appropriate number of 4's and 5's" (IH), and k≥12.
Show: P(k+4) = "we can get amount k+4 by summing up an appropriate number of 4's and 5's".
Let a and b be the appropriate number of 4's and 5's to get the amount k. So, we have that k = 4a + 5b. (We know these exist because of the IH.)
The number of 4's and 5's to get the amount k+4 is (a+1) and b, respectively, because k+4 = 4(a+1) + 5b.
Which is what we had to prove!
(*) The induction is sound since we prove P(12),P(13),P(14),P(15) as base cases, and P(k)=>P(k+4) as step case, which allows us to reach any natural number ≥12.
(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.