Discrete Mathematics for Computer Scientists -- Exercises Week 3 - Induction

Discrete Mathematics for Computer Scientists -- Exercises Week 3 - Induction - Answers	DIT980, HT 2016
Home \| Schedule \| Assignments \| Exercises \| Book \| Exam \| About	Fire \| Forum \| TimeEdit \| Links

Exercises Week 3 - Induction - Answers Here are some answers for the exercises. 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. Let P(n) = "8ⁿ - 3ⁿ is divisable by 5". Base case: P(1): 8¹ - 3¹ = 5, which is divisable by 5. Step case: P(n) => P(n+1), for n≥1. Assume: P(n) = "8ⁿ - 3ⁿ is divisable by 5" (IH), and n≥1. Show: P(n+1) = "8ⁿ⁺¹ - 3ⁿ⁺¹ is divisable by 5". Now look at: 8ⁿ⁺¹ - 3ⁿ⁺¹ = 8⋅8ⁿ - 3⋅3ⁿ = (5+3)⋅8ⁿ - 3⋅3ⁿ = 5⋅8ⁿ + 3⋅8ⁿ - 3⋅3ⁿ = 5⋅8ⁿ + 3⋅(8ⁿ - 3ⁿ) This is divisable by 5, because it is the sum of 5⋅8ⁿ (which is divisable by 5) and 3⋅(8ⁿ - 3ⁿ) (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(n) => P(n+1), for n≥1. Assume: P(n) = "1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3" (IH), and n≥ 1. Show: P(n+1) = "1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) + (n+1)⋅(n+2) = (n+1)(n+2)(n+3)/3". Now look at: 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n+1) + (n+1)(n+2) = n(n+1)(n+2)/3 + (n+1)(n+2) (because of IH) = n(n+1)(n+2)/3 + 3(n+1)(n+2)/3 = (n(n+1)(n+2) + 3(n+1)(n+2))/3 = (n+1)(n+2)(n+3)/3 Which is what we had to prove! 4. To prove: 4n < 2ⁿ, for all n ≥ 5. Proof: By induction. Let P(n) = "4n < 2ⁿ". Base case: P(5): 4⋅5 = 20 < 32 = 2⁵. OK! Step case: P(n) => P(n+1), for n≥5. Assume: P(n) = "4n < 2ⁿ" (IH), and n≥5. Show: P(n+1) = "4(n+1) < 2ⁿ⁺¹". Look at: 4(n+1) = 4n + 4 < 2ⁿ + 4 (because of IH) < 2ⁿ + 2ⁿ (because n > 2) = 2⋅2ⁿ = 2ⁿ⁺¹ 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. Let P(n) = "the n-th derivative of xⁿ is n!". Base case: P(1). The (1st) derivative of x¹ is 1, which equals 1!. OK! Step case: P(n) => P(n+1), for n≥1. Assume: P(n) = "the n-th derivative of xⁿ is n!" (IH), and n≥1. Show: P(n+1) = "the (n+1)-th derivative of xⁿ⁺¹ is (n+1)!". Look at: the (n+1)-th derivative of xⁿ⁺¹ = the n-th derivative of [ (n+1)xⁿ ] = (n+1) ⋅ [ the n-th derivative of xⁿ ] = (n+1) ⋅ n! (because of IH) = (n+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. Let P(n) = "f(x,n) = xⁿ, for all x>0". Base case: P(0): f(x,0) = 1 = x⁰. OK! Step case: (∀0≤k≤n . P(k)) => P(n+1), for n≥0. Assume: for 0≤k≤n: P(k) = "f(x,k) = x^k, for all x>0" (IH), and n≥0. Show: P(n+1) = "f(x,n+1) = xⁿ⁺¹, for all x>0" Now we do a case split. Case 1: (n+1) is even. Now look at: f(x,n+1) = f(x,(n+1)/2)² = (x^(n+1)/2)² (because of IH, k=(n+1)/2 < n) = xⁿ⁺¹, which is what we had to prove! Case 2: (n+1) is odd. Now look at: f(x,n+1) = x ⋅ f(x,n+1-1) = x ⋅ f(x,n) = x ⋅ (xⁿ) (because of IH, k=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. 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: (∀1≤k≤n . P(k)) => P(n+1), for n≥1. Assume: for 1≤k≤n: P(k) = "to break a bar of chocolate with k squares into squares only, we need k-1 breaks" (IH), and n≥1. Show: P(n+1) = "to break a bar of chocolate with n+1 squares into squares only, we need n breaks" Since we have more than one square (n+1>1), we need to do at least one break. This leaves us with two new chocolate bars, of with n1 and n2 squares, respectively. The total number of squares does not change, so n1+n2=n+1. We know that 1 ≤ n1 ≤ n and also 1 ≤ n2 ≤ n. By using the IH twice (on n1 and n2), we know that to break each of these into squares would require n1-1 breaks and n2-1 breaks, respectively. So, the total number of breaks is 1 + (n1-1) + (n2-1) = n1+n2 - 1 = (n+1) - 1 = n. (This holds 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 (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(n) => P(n+4), for n≥12. Assume: P(n) = "we can get amount n by summing up an appropriate number of 4's and 5's" (IH), and n≥12. Show: P(n+4) = "we can get amount n+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 n. So, we have that n = 4a + 5b. (We know these exist because of the IH.) The number of 4's and 5's to get the amount n+4 is (a+1) and b, respectively, because n+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(n)=>P(n+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.

Discrete Mathematics for Computer Scientists -- Exercises Week 3 - Induction - Answers	DIT980, HT 2016
Home \| Schedule \| Assignments \| Exercises \| Book \| Exam \| About	Fire \| Forum \| TimeEdit \| Links

Exercises Week 3 - Induction - Answers Here are some answers for the exercises. 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. Let P(n) = "8ⁿ - 3ⁿ is divisable by 5". Base case: P(1): 8¹ - 3¹ = 5, which is divisable by 5. Step case: P(n) => P(n+1), for n≥1. Assume: P(n) = "8ⁿ - 3ⁿ is divisable by 5" (IH), and n≥1. Show: P(n+1) = "8ⁿ⁺¹ - 3ⁿ⁺¹ is divisable by 5". Now look at: 8ⁿ⁺¹ - 3ⁿ⁺¹ = 8⋅8ⁿ - 3⋅3ⁿ = (5+3)⋅8ⁿ - 3⋅3ⁿ = 5⋅8ⁿ + 3⋅8ⁿ - 3⋅3ⁿ = 5⋅8ⁿ + 3⋅(8ⁿ - 3ⁿ) This is divisable by 5, because it is the sum of 5⋅8ⁿ (which is divisable by 5) and 3⋅(8ⁿ - 3ⁿ) (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(n) => P(n+1), for n≥1. Assume: P(n) = "1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3" (IH), and n≥ 1. Show: P(n+1) = "1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) + (n+1)⋅(n+2) = (n+1)(n+2)(n+3)/3". Now look at: 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n+1) + (n+1)(n+2) = n(n+1)(n+2)/3 + (n+1)(n+2) (because of IH) = n(n+1)(n+2)/3 + 3(n+1)(n+2)/3 = (n(n+1)(n+2) + 3(n+1)(n+2))/3 = (n+1)(n+2)(n+3)/3 Which is what we had to prove! 4. To prove: 4n < 2ⁿ, for all n ≥ 5. Proof: By induction. Let P(n) = "4n < 2ⁿ". Base case: P(5): 4⋅5 = 20 < 32 = 2⁵. OK! Step case: P(n) => P(n+1), for n≥5. Assume: P(n) = "4n < 2ⁿ" (IH), and n≥5. Show: P(n+1) = "4(n+1) < 2ⁿ⁺¹". Look at: 4(n+1) = 4n + 4 < 2ⁿ + 4 (because of IH) < 2ⁿ + 2ⁿ (because n > 2) = 2⋅2ⁿ = 2ⁿ⁺¹ 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. Let P(n) = "the n-th derivative of xⁿ is n!". Base case: P(1). The (1st) derivative of x¹ is 1, which equals 1!. OK! Step case: P(n) => P(n+1), for n≥1. Assume: P(n) = "the n-th derivative of xⁿ is n!" (IH), and n≥1. Show: P(n+1) = "the (n+1)-th derivative of xⁿ⁺¹ is (n+1)!". Look at: the (n+1)-th derivative of xⁿ⁺¹ = the n-th derivative of [ (n+1)xⁿ ] = (n+1) ⋅ [ the n-th derivative of xⁿ ] = (n+1) ⋅ n! (because of IH) = (n+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. Let P(n) = "f(x,n) = xⁿ, for all x>0". Base case: P(0): f(x,0) = 1 = x⁰. OK! Step case: (∀0≤k≤n . P(k)) => P(n+1), for n≥0. Assume: for 0≤k≤n: P(k) = "f(x,k) = x^k, for all x>0" (IH), and n≥0. Show: P(n+1) = "f(x,n+1) = xⁿ⁺¹, for all x>0" Now we do a case split. Case 1: (n+1) is even. Now look at: f(x,n+1) = f(x,(n+1)/2)² = (x^(n+1)/2)² (because of IH, k=(n+1)/2 < n) = xⁿ⁺¹, which is what we had to prove! Case 2: (n+1) is odd. Now look at: f(x,n+1) = x ⋅ f(x,n+1-1) = x ⋅ f(x,n) = x ⋅ (xⁿ) (because of IH, k=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. 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: (∀1≤k≤n . P(k)) => P(n+1), for n≥1. Assume: for 1≤k≤n: P(k) = "to break a bar of chocolate with k squares into squares only, we need k-1 breaks" (IH), and n≥1. Show: P(n+1) = "to break a bar of chocolate with n+1 squares into squares only, we need n breaks" Since we have more than one square (n+1>1), we need to do at least one break. This leaves us with two new chocolate bars, of with n1 and n2 squares, respectively. The total number of squares does not change, so n1+n2=n+1. We know that 1 ≤ n1 ≤ n and also 1 ≤ n2 ≤ n. By using the IH twice (on n1 and n2), we know that to break each of these into squares would require n1-1 breaks and n2-1 breaks, respectively. So, the total number of breaks is 1 + (n1-1) + (n2-1) = n1+n2 - 1 = (n+1) - 1 = n. (This holds 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 (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(n) => P(n+4), for n≥12. Assume: P(n) = "we can get amount n by summing up an appropriate number of 4's and 5's" (IH), and n≥12. Show: P(n+4) = "we can get amount n+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 n. So, we have that n = 4a + 5b. (We know these exist because of the IH.) The number of 4's and 5's to get the amount n+4 is (a+1) and b, respectively, because n+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(n)=>P(n+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.