CMPS 211 Homework Assignment 07 Solution, Fall 2014

CMPS 211 – Fall 2014 Assignment 7 Solution 1 Assignment 7 Solution Ex1: 𝑓(1) = 1 2 = 21 − 1 21 𝑓(2) = 3 4 = 22 − 1 22 𝑓(3) = 7 8 = 23 − 1 23 Conjecture: 𝑓(𝑛) = 2𝑛 − 1 2𝑛 Proof: Assume true for n, prove it is true for n+1 𝑓(𝑛 + 1) = 𝑓(𝑛) + 1 2𝑛+1 [? = 2𝑛+1 − 1 2𝑛+1 ] 𝑓(𝑛 + 1) = 2𝑛 − 1 2𝑛 + 1 2𝑛+1 = 2 ∗ (2𝑛 − 1) + 1 2𝑛+1 = 2𝑛+1 − 1 2𝑛+1 Proved! Ex2: RTP: 6 divides 𝑛3 − 𝑛 whenever n is a non-negative integer  try for n = 0, and n =1, 𝑛3 − 𝑛 = 0, which can be divided by 6 [0= 6k, for k belongs to Z, k =0]  try for n = 2, and n =1, 𝑛3 − 𝑛 = 8 − 2 = 6 , which can be divided by 6 also [6= 6k, for k belongs to Z, k =1] 𝑛3 − 𝑛 = 𝑛 (𝑛2 − 1) = (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) Now,  if n is even, then n = 2k for some k belongs to Z  if n is odd, then n=2k+1, then n-1 = 2k, for some k belongs to Z  ==>, whether n is odd or even, (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) is divisible by 2, i.e : (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) = 2𝑗 for some j belongs to Z CMPS 211 – Fall 2014 Assignment 7 Solution 2  if n is divisible by 3, then n = 3m for some m belongs to Z  else if n is not divisible by 3, then n=3m+1, or n=3m+2 for some m belongs to Z o if n = 3m+1, then n-1 = 3m, then n-1 is divisible by 3 o if n = 3m+2, then n+1 = 3m+3 = 3(m+1), then n+1 is divisible by 3  ==> whether n is divisible by 3 or not, (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) is divisible by 3, i.e : (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) = 3𝑖 for some i belongs to Z  then (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1)is always divisible by 2 and 3, then  𝑛3 − 𝑛 = (𝑛 − 1) ∗ 𝑛 ∗ (𝑛 + 1) = 2 ∗ 3 ∗ 𝑝 = 6𝑝, for some p belongs to Z Then 𝑛3 − 𝑛 is always divisible by 6 Ex3: The problem is that it wasn’t verified on a base case. For n = 1, ∑ 𝑖 1 𝑖=1 = 1, but according to the given formula, ∑ 𝑖 1 𝑖=1 = (1+1 2) 2 2 = 1.125, so it fails on base cases. Ex4: Base Case: n = 1, m > 1, f : {1,2…m}  {1}, then there exists more than one value in the domain that maps to 1, then f is not 1:1 by definition Inductive Step: Assume for all n < m, f : {1,2…m}  {1, 2, … n}, then f is not 1:1 Show that it’s still holds for n+1 < m, i.e: f : {1,2…m}  {1, 2, … n+1} is also not 1:1 Case 1: if no value in domain maps to n+1, then the range can be shrunk to {1, 2…n}, then f is not 1:1 from inductive step Case 2: if more than 1 value in domain maps to n+1, then f is not 1:1 by def Case 3: exactly 1 value (k) from domain maps to n+1, then we can remove k from domain and n+1 from range [and replace k by m, without affecting the function], to have f: {1,2 … m-1}  {1, 2…n}, i.e: f: {1,2 … m’}  {1, 2…n}, and m-1 > n since m > n+1, then f is not 1:1 by inductive hypothesis Then in all cases f is not 1:1 when n < m Ex5: a) By using the 4-cent stamps, we can have 4, 8, 12, 16, 20, 24… Starting with a 7, and by adding 4, we can have 7, 11, 15, 19, 23… Starting with 2 7s, we can have 14, 18, 22… CMPS 211 – Fall 2014 Assignment 7 Solution 3 By starting with 3 7s, we can have 21, 25, 29… Since we had 4 numbers in a row, we can know the numbers that can be formed. We have 18, 19, 20 and 21  For n ≥ 18, we can right any number by using only 4s and 7s and to prove that we use induction and strong induction in part b) and c)  The numbers that can be formed are 4, 7, 8, 11, 12, 14, 15, 16 and any n ≥ 18 b) RTP: For all k >= 18, k = 4a + 8b for a,b >= 0 18 = 2(7) + 4 [basis step] Assume it’s true for k, prove its true for k+1 Case 1: if k has one of more 7s (b>0), then b-1 > 0, 4(a+2) + 7(b-1) = 4a + 7b +1 = k+1 Case 2: if k has no 7s (b=0, k = 4a), then a >= 5, since k>=18, and 18 = 4a, then a>= 4.5, but a is integer, then a >= 5 Then a-5 >= 0, then 4(a-5) + 7(3) = 4a + 1 = k+1 Then in both cases we can move from build k+1 from stamps of 4 and 7 if k>=18, by induction c) RTP: we can right any number above 18 by only using 4s and 7s Let P(n) be the proposition that postage of n cents can be formed using 4-cent and 7-cent stamps - P(18) uses 2 7s and 1 4 [basis] - P(19) uses 1 7 and 3 4s [basis] - P(20) uses 5 4s [basis] - P(21) uses 3 7s [basis] Suppose P(j) holds for 18 ≤ j ≤ k where k ≥ 21 [inductive step] [hypothesis] RTP: P(k+1) holds k ≥ 21 => k – 3 ≥ 18  We can form k – 3 by only using 7s and 4s  By adding only 4, we form k + 1 by only using 7s and 4s In the mathematical induction, we supposed for a particular k that the hypothesis works, while in the strong induction we supposed that for all the values between 18 and k the hypothesis works Ex6: Base Case: 1 = 20, 3 = 20+ 21 RTP: Any integer can be written as sum of distinct powers of 2 CMPS 211 – Fall 2014 Assignment 7 Solution 4 Inductive step: Assume that 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑘 ≤ 𝑛, 𝑘 = 2𝑏0 + 2𝑏1 + ⋯ + 2𝑏𝑚−1 + 2𝑏𝑚, 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑎𝑙𝑙 𝑏𝑖𝑠 𝑎𝑟𝑒 𝑑𝑖𝑠𝑡𝑖𝑛𝑐𝑡 𝑣𝑎𝑙𝑢𝑒𝑠 Show that k+1 can also be written as a sum of distinct powers of 2 Case 1: if k is even, then there is no bi=0, since 2x is even for all x > 0, and sum of even numbers is even, so k can have 20 in its sum… and k+20 = k+1, then k+1 can be written as sum of distinct powers of 2 Case 2: if k is odd, then k+1 is even, then (k+1)/2 can be written as sum of distinct powers of 2 (By Strong Induction Hypothesis), then k+1 2 = 2𝑏0 + 2𝑏1 + ⋯ + 2𝑏𝑚−1 + 2𝑏𝑚 where the powers of 2 are distinct then (k + 1) = 2 ∗ (2𝑏0 + 2𝑏1 + ⋯ + 2𝑏𝑚−1 + 2𝑏𝑚) = 21+𝑏0 + 21+𝑏1 + ⋯ + 21+𝑏𝑚−1 + 21+𝑏𝑚, then the powers of 2 are still distinct then k+1 can be written as sum of distinct powers of 2 in the two cases, k+1 can be written as sum of distinct powers of 2 Ex7: RTP: 2𝑛2 − 10𝑛 + 4 ≥ 0 𝑤ℎ𝑒𝑛𝑒𝑣𝑒𝑟 𝑛 ≥ 5 Base case: n =5, 2𝑛2 − 10𝑛 + 4 = 4 ≥ 0, 𝑠𝑜 𝑡𝑟𝑢𝑒 Assume it holds for n, prove it true for n+1 𝑓(𝑛 + 1) = 2(𝑛 + 1)2 − 10(𝑛 + 1) + 4 = 2(𝑛2 + 2𝑛 + 1) − 10𝑛 − 10 + 4 = 2𝑛2 + 4𝑛 + 2 − 10𝑛 − 10 + 4 = 𝑓(𝑛) + 4𝑛 − 8 now, is 𝑓(𝑛) + 4𝑛 − 8 ≥ 0 𝑓𝑜𝑟 𝑛 ≥ 5 ? 𝑛 ≥ 5 𝑡ℎ𝑒𝑛 4𝑛 ≥ 20 𝑡ℎ𝑒𝑛 4𝑛 − 8 ≥ 12 ≥ 0 𝑺𝒐: 𝑓(𝑛) ≥ 0 𝑎𝑛𝑑 4𝑛 − 8 ≥ 0 𝑓𝑜𝑟 𝑛 ≥ 5, 𝑡ℎ𝑒𝑛 𝑓(𝑛 + 1) ≥ 0 𝑓𝑜𝑟 𝑛 ≥ 5 then n =5, 2𝑛2 − 10𝑛 + 4 ≥ 0, 𝑓𝑜𝑟 𝑛 ≥ 5 𝑏𝑦 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 Ex8: RTP: (A1∩A2∩···∩An) ∪ B = (A1∪B) ∩ (A2∪B) ∩···∩ (An ∪ B) Base Case: For n=1, A1∪B = A1∪B P(k) = (A1∩A2∩···∩Ak) ∪ B, Q(k) = (A1∪B) ∩ (A2∪B) ∩···∩ (Ak ∪ B), CMPS 211 – Fall 2014 Assignment 7 Solution 5 Inductive Step: Assume P(k) = Q(k), show P(k+1) = Q(k+1) Q(k+1) = (A1∪B) ∩ (A2∪B) ∩···∩ (Ak ∪ B) ∩ (Ak+1 ∪ B) = Q(k) ∩ (Ak+1 ∪ B) = P(k) ∩ (Ak+1 ∪ B) = P(k) ∩ (Ak+1 ∪ B) = ((A1∩A2∩···∩Ak) ∪ B) ∩ (Ak+1 ∪ B) = ((A1∪B) ∩ (A2∪B) ∩···∩ (Ak ∪ B)) ∩ (Ak+1 ∪ B) = (A1∪B) ∩ (A2∪B) ∩···∩ (Ak ∪ B) ∩ (Ak+1 ∪ B) Proved Ex9: 𝑛3 + (𝑛 + 1)3 + (𝑛 + 2)3 = 3(𝑛3 + 3𝑛2 + 5𝑛 + 3) (𝑛 + 1)3 + (𝑛 + 2)3 + (𝑛 + 3)3 = 3(𝑛3 + 6𝑛2 + 14𝑛 + 12)