CMPS 211 Homework 2 with Solution, Fall 2010

CMPS 211 Fall 2010 Assignment II - Solution Section 4.1 4- P(n) : 13 + 23 + 33 + …. + n3 = 2 2 )1 ( ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ n n + a) P(1) : 13 = 2 2 )1 1(1 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + b) 2 2 )1 1(1 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + = 2 2 2 ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = 12 = 1 = 13 ⇒ P(1) is true. c) Inductive Hypothesis: 13 + 23 + 33 + …. + n3 = 2 2 )1 ( ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ n n + d) Assuming the inductive hypothesis in (c), need to show that 13 + 23 + 33 + …. + n3 + (n+1)3 = 2 2 2) 1)( ( ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + + n n e) 13 + 23 + 33 + …. + n3 + (n+1)3 = 2 2 )1 ( ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ n n + + (n+1)3 by inductive hypothesis = (n+1)2 ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ + ⎟ + ⎠ ⎞ ⎜ ⎝ ⎛ )1 ( 2 2 n n = (n+1)2 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + + 2 2 2 4 4n n = (n+1)2 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + 2 2 2 2) (n = 2 2 2) 1)( ( ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + + n n f) By completing the basis step and the inductive step, we’ve shown that this statement is true for all positive integers n. 6- 1⋅1! + 2⋅2! + …. +n⋅n! = (n+1)! – 1 Basis step: 1⋅1! = 1 (1+1)! – 1 = 2! – 1 = 2 – 1 = 1 ⇒ 1⋅1! = (1+1)! – 1. Inductive Hypothesis: 1⋅1! + 2⋅2! + …. +n⋅n! = (n+1)! – 1 Inductive Step: Show that 1⋅1! + 2⋅2! + …. +n⋅n! + (n+1)⋅(n+1)! = (n+2)! – 1 ? 1⋅1! + 2⋅2! + …. +n⋅n! + (n+1)⋅(n+1)! = (n+1)! – 1 + (n+1)⋅(n+1)! = (n+1)! [1+(n+1)] – 1 = (n+1)! (n+2) – 1 = (n+2)! – 1 10- a) Formula for )1 ( 1 ... 2 3 1 1 2 1 + + + ⋅ + ⋅ n n For n = 1: 2 1 1 2 1 = ⋅ For n = 2: 3 2 6 4 6 1 2 1 2 3 1 1 2 1 = = + = ⋅ + ⋅ For n = 3: 4 3 12 9 12 1 6 1 2 1 3 4 1 2 3 1 1 2 1 = = + + = ⋅ + ⋅ + ⋅ For positive integers n: )1 ( 1 ... 2 3 1 1 2 1 + + + ⋅ + ⋅ n n = n +1 n b) Show )1 ( 1 ... 2 3 1 1 2 1 + + + ⋅ + ⋅ n n = n +1 n Basis Step: shown in part (a) above for n = 1 Inductive Hypothesis: )1 ( 1 ... 2 3 1 1 2 1 + + + ⋅ + ⋅ n n = n +1 n Inductive Step: Show 2) 1)( ( 1 )1 ( 1 ... 2 3 1 1 2 1 + + + + + ⋅ + + ⋅ n n n n = 2 1 + + n n 2) 1)( ( 1 )1 ( 1 ... 2 3 1 1 2 1 + + + + + + ⋅ + ⋅ n n n n = 2) 1)( ( 1 1 + + + + n n n n = 2) 1)( ( 1 2) ( + + + + n n n n = 2) 1)( ( 1 2 2 + + + + n n n n = 2) 1)( ( )1 ( 2 + + + n n n = 2 1 + + n n 16 - 1·2·3 + 2·3·4 +...+ n(n+1)(n+2)= ���������������� � Basis Step: true for n=1, P(1) true, 1·2·3= ���������������� � , 6 = 6 Inductive Step: Suppose that P(k) is true, k > 0 1·2·3+ 2·3·4+...+ k(k+1)(k+2)= ���������������� � Show that P(k+1) is true 1·2·3+ 2·3·4+...+ k(k+1)(k+2) + (k+1)(k+2)(k+3) = ���������������� � + (k+1)(k+2)(k+3) (by inductive hypothesis) =(k+1)(k+2)(k+3)� � � � 1� =(k+1)(k+2)(k+3) � ��� � � 32- = ����������� � Therefore, P And 1·2·3+ Prove tha Basis Step Inductive Inductive (n+1)3+2( But (n3 + and 3(n2+ So, (n3 + ⇒ ∴ ���������� � P(k+1) true. + 2·3·4+...+ n at 3 divides n p: (n=1) Hypothesis Step: Show (n+1) = n3 + = n3 + = (n3 = (n3 2n) is divisi +n+1) is divi 2n)+ 3(n2+n ⇒ (n+1)3+2(n 3 divides n3 as required. n(n+1)(n+2)= n3+2n for all 13+2 = 1+2 ⇒ True for : n3+2n is di w that (n+1)3+ + 3n2 + 3n + + 3n2 + 5n + + 2n)+ 3n2 + + 2n)+ 3(n2 ible by 3 sible by 3 n+1) is divisi n+1) is divisi 3+2n for all . = ���������� � n>0. 2 = 3 d r n=1. ivisible by 3 +2(n+1) is d 1 + 2n + 2 + 3 + 3n + 3 2+n+1) b m ible by 3. ible by 3 n>0 ������� , n>0 divisible by . divisible by 3 by inductive multiplied b . 3 3. e hypothesis y 3 Section 4.2 4- P(n): a postage of n cents can be formed using 4-cent stamps and 7-cent stamps Show P(n) is true for all n ≥ 18. a) P(18) : 18 = 4+14 = 4⋅1 + 7⋅2 ⇒ True for n=18 P(19) : 18 = 12+7 = 4⋅3 + 7⋅1 ⇒ True for n=19 P(20) : 20 = = 4⋅5 + 7⋅0 ⇒ True for n=20 P(21) : 21 = = 4⋅0 + 7⋅3 ⇒ True for n=21 b) Inductive Hypothesis: P(n) is true for all 18 ≤ n ≤ k, i.e. P(n) = 4k1 + 7k2 for some k1 , k2 ≥ 0 c) Inductive Step: Required to prove that P(k+1) is true for k ≥ 22. d) P(k+1) = P(k) + 1 = P(k–1) + 2 = P(k–2) + 3 = P(k–3) + 4 But P(k–3) is true by inductive hypothesis i.e. P(k–3) = 4k1 + 7k2 for some k1 , k2 ≥ 0 So P(k+1) = 4k1 + 7k2 + 4 = 4(k1 +1) + 7k2 ⇒ P(k+1) is true for all k ≥ 22 ∴ P(n) is true for all n≥ 18. 8. We c Let P by 5 The b exam Induc P(1), For n certif n+1 > 5(n - certif resem certif There claim that ev P(n) be the st from 140$ u basis step is mined and the ctive Hypoth P(2), P(3),a n + 1, we nee ficates. > 5 so 140+5 4) is P(n - 4 ficates of the mbling P(n+1 ficates of the efore, P(n) is ery amount tatement that up to 140$+5 proved in th e statement p hesis: Suppo and P(4)) are ed to show th 5(n+1) = 140 4) which is tr e 25 dollars a 1) can be for e 40 dollars. s true for all divisible by t the amount 5n$ can be fo he table abov proven true f ose that P is t e proven true hat 140 + 5(n 0+5n+5 = 14 rue by induc and k2 gift ce rmed of (k1 + Thus, P(n+1 the values c 5 and above ts in the tabl ormed from ve, all possib for these val true for all n e. n + 1) can b 40+5(n-4)+2 ctive hypothe ertificates of +1) gift certi 1) is true. claimed abov e 140$ is ava le above and the gift certi ble quantities lues. numbers up t e formed fro 20+5 = 140 + esis and can f the 40 doll ificates of th ve. ailable. d every amou ificates. s under 160$ to n, where n om 25 and 40 + 5(n - 4) + 2 be formed o ars. So, the n he 25 dollars unt divisible $ were n > 4, (P(0), 0 dollar 25 but 140 + of k1 gift new quantity and k2 gift + y Section 4.3 4- a) f(n+1) = f(n) – f(n-1) f(0) = f(1) = 1 f(2) = f(1) – f(0) = 1 – 1 = 0 f(3) = f(2) – f(1) = 0 – 1 = -1 f(4) = f(3) – f(2) = (-1) – 0 = -1 f(5) = f(4) – f(3) = (-1) – (-1) = 0 b) f(n+1) = f(n) f(n-1) f(0) = f(1) = 1 f(2) = f(1) f(0) = (1) (1) = 1 f(3) = f(2) f(1) = (1) (1) = 1 f(4) = f(3) f(2) = (1) (1) = 1 f(5) = f(4) f(3) = (1) (1) = 1 c) f(n+1) = f(n)2 + f(n-1)3 f(0) = f(1) = 1 f(2) = f(1)2 + f(0)3 = (1)2 + (1)3 = 1 + 1 = 2 f(3) = f(2)2 + f(1)3 = (2)2 + (1)3 = 4 + 1 = 5 f(4) = f(3)2 + f(2)3 = (5)2 + (2)3 = 25 + 8 = 33 f(5) = f(4)2 + f(3)3 = (33)2 + (5)3 = 1089 + 125 = 1214 d) f(n+1) = f(n) / f(n-1) f(0) = f(1) = 1 f(2) = f(1) / f(0) = 1 / 1 = 1 f(3) = f(2) / f(1) = 1 / 1 = 1 f(4) = f(3) / f(2) = 1 / 1 = 1 f(5) = f(4) / f(3) = 1 / 1 = 1 6- a) f(0) = 1, f(n) = – f(n-1) for n ≥ 1 Valid: f(n) = (– 1)n for n ≥ 1 Proof: Basis Step: f(1) = (–1)1 = –1 Inductive Hypothesis: f(n) = (– 1)n for n ≥ 1 Inductive Step: f(n+1) = – f(n) = – (– 1)n = (– 1) (– 1) n = (– 1) n+1 d) f(0) = 0, f(1) = 1 f(n) = 2 f(n-1) for n ≥ 1 Not Valid: defined starting at n=1, but f(1) = 2 f(0) = 2⋅ 0 = 0 ≠ 1. e) f(0) = 2, f(n) = f(n-1) if n is odd and n ≥ 1 f(n) = 2 f(n-2) if n ≥ 2 Valid: f(n) = ⎪⎩ ⎪⎨ ⎧ ≥ ≥ + + 0 if n is odd and n 2 if n is even and n 0 2 1) / 2 (n (n 2) / 2 Proof: Basis Step: f(0) = 2 (0+2) / 2 = 21 = 2 f(1) = 2 (1+1) / 2 = 21 = 2 = f(0) Inductive Hypothesis: f(n) = ⎪⎩ ⎪⎨ ⎧ ≥ ≥ + + 0 if n is odd and n 2 if n is even and n 0 2 1) / 2 (n (n 2) / 2 Inductive Step: • n is even ⇒ f(n) = 2 (n+2) / 2 ⇒ n+1 is odd ⇒ Show f(n+1) = 2 (n+1 +1) / 2 = 2 (n+2) / 2 f(n+1) = f((n+1)-1) (by recursive definition) = f(n) = 2 (n+2) / 2 (by induction hypothesis) True • n is odd ⇒ f(n) = 2 (n+1) / 2 ⇒ n+1 is even ⇒ Show f(n+1) = 2 (n+1 +2) / 2 = 2 (n+3) / 2 f(n+1) = 2 f((n+1)-1) (by recursive definition) = 2 f(n) = 2⋅ 2 (n+1) / 2 (by induction hypothesis) = 2 (n+1) / 2 + 1 = 2 (n+1 +2) / 2 = 2 (n+3) / 2 True 10- Sm(n) is the sum of the integer m and the nonnegative integer n. Sm(0) = m, Sm(1) = m+1, Sm(2) = m+2 = (m+1)+1, … Recursive Definition: Sm(0) = m, Sm(n) = Sm(n-1) + 1 for n ≥ 1. 12- fn is the nth Fibonacci number. Show f1 2 + f2 2 + … + fn 2 = fn fn+1 (using induction). Let P(n) be the statement “f1 2 + f2 2 + … + fn 2 = fn fn+1”. Basis Step: P(1) is true because f1 2 = f1 f1 = f1 f2 since f1 = f2 = 1. Inductive Hypothesis: Assume P(n) is true, i.e. f1 2 + f2 2 + … + fn 2 = fn fn+1 Inductive Step: Show that P(n+1) is true, i.e. f1 2 + f2 2 + … + fn 2 + fn+1 2 = fn+1 fn+2 P(n+1) = f1 2 + f2 2 + … + fn 2 + fn+1 2 = P(n) + fn+1 2 = fn fn+1 + fn+1 2 (by inductive hypothesis) = fn+1 ( fn + fn+1 ) = fn+1 fn+2 (by Fibonacci formula) Thus, f1 2 + f2 2 + … + fn 2 = fn fn+1 is true for all n ≥ 1. 22 - Let A be the set of positive integers. We will show that S = A. We will show that A ⊆ S and S ⊆ A. We will first show that A is a subset of S. Let P(n) be the statement that n belongs to S, where n is an element in A. Basis Step: n = 1, true since 1 ∈ S Hypothesis: Suppose P(k) is true, i.e. k ∈ S Inductive Step: Show that P(k + 1) is true. P(k + 1) is true if (k + 1) ∈ S, but k + 1 = (k) + (1), where k ∈ S and 1 ∈ S and thus (k + 1) ∈ S. P(n) is true and A ⊆ A. To show that S ⊆ A, we'll show that the base step of S is in A and elements generated by the recursive formula are in A as well, i.e. (s + t) ∈ A whenever s ∈ S and t ∈ S. 1 ∈ A, since 1 is a positive integer. Let s, t ∈ S; s and t are positive integers and their sum s + t = k is positive. Since k is a positive integer, then k ∈ A, (A is the set of all positive integers). Therfeore, A = S. 24- a) the set of odd positive integers: set S 1 ∈ S, and if x ∈ S then x+2 ∈ S. b) the set of positive integer powers of 3: set S 1=30 ∈ S, and if x ∈ S then 3x ∈ S c) the set of polynomials with integer coefficients: set S c0 x0 ∈ S, and if c0 x0 + c1 x1 +…+ cn xn ∈ S then c0 x0 + c1 x1 +…+ cn xn + cn+1 xn+1 ∈ S where ci ∈ N, i ≥ 0 26- S is the subset of the set of ordered pairs of integers defined recursively by Basis Step: (0,0) ∈ S. Recursive Step: If (a,b) ∈ S, then (a+2,b+3) ∈ S and (a+3,b+2) ∈ S. a) (2,3) , (3,2) ; (4,6) , (5,5) , (6, 4) ; (6,9) , (7,8) , (8,7) , (9,6); (8,12) , (9,11) , (10,10) , (11,9) , (12,8) ; (10,15) , (11,14) , (12,13) , (13,12) , (14,11) , (15,10). b) Let P(n) be the statement that 5 divides a+b whenever (a,b) ∈ S is obtained by n applications of the recursive step. Basis Step: P(0) is true because 5 divides 0+0 and (0,0) ∈ S obtained with 0 steps of the recursion. Inductive Step: Assume P(k) is true, i.e. 5 divides a+b whenever (a,b) ∈ S is obtained by k or less applications of the recursive step. Show P(k+1) is true, i.e. it’s valid for an element obtained with k+1 applications of the recursion. So 5 divides a+b (which is obtained by fewer iterations), and applying the final recursive step results in (a+2,b+3) and (a+3,b+2). Case 1: a+2 + b+3 = a+b +5 = (a+b) +5 divisible by 5. Case 1: a+3 + b+2 = a+b +5 = (a+b) +5 divisible by 5. 32- a) ones(s) : counts the number of ones in a bit string s. Let x be a single bit, i.e. x ∈ {0,1}. Let s be a bit string, i.e. s ∈ {0,1}*. ones(x) = ⎩ ⎨ ⎧ = = 1 0 1 1 if x if x Then, s = tx where t is also a bit string, and |t| = |s|-1. So, ones(s) = ones(t x) = ones(t) + ones(x). 50- A(1,n) = 2n for n ≥ 1. Let P(n) be the statement “A(1,n) = 2n ” for n ≥ 1. Basis Step: P(1) is true because A(1,1) = 2 according to Ackermann’s function and A(1,1) = 21 = 2 according to P(1) Inductive Step: Assume P(k) is true for k ≥ 1, i.e. A(1,k) = 2k Show that P(k+1) is true, i.e. A(1,k+1) = 2k+1 A(1,k+1) = A(0, A(1,k)) according to Ackermann’s function – rule 4 = A(0,2k) according to induction hypothesis = 2 (2k) according to Ackermann’s function – rule 1 = 2k+1 Thus, using the basis step and the inductive step, and by the principle of mathematical induction, A(1,n) = 2n for n ≥ 1. Section 3.1 4- procedure maxDiff (a1, a2, …, an: integers) diff := 0 maxDiff := 0 for i := 1 to n-1 diff := ai – ai+1 if absValue (diff) > maxDiff then maxDiff := absValue (diff) {maxDiff has the desired value} 6- procedure numNegative (a1, a2, …, an: integers) count := 0 for i := 1 to n if ai < 0 then count := count + 1 {count has the desired value} 10- procedure powerNonNeg (x: real; n: positive integer) power := 1 for i := 1 to n power := power × x {power has the desired value, and this is a subprocedure being called by another} procedure power (x:real; n: integer) power := powerNonNeg (x, absValue(n)) if n < 0 then power := 1 / power {power has the desired value, for all negative and nonnegative powers} 18- procedure lastSmallest (a1, a2, …, an: integers) smallest := a1 smallestLoc := 1 for i := 2 to n if ai ≤ smallest then begin smallest := ai smallestLoc := i end {smallestLoc has the desired value} 32- procedure greaterTerms (s1, s2, …, sn: integers) sum := s1 termList := {} for i := 2 to n if ai > sum then termList := termList ∪ si sum := sum + si {termList has the desired set} 34 - The lists obtained at each step are: i = 1; j = 1; (2; 6; 3; 1; 5; 4) i = 1; j = 2; (2; 3; 6; 1; 5; 4) i = 1; j = 3; (2; 3; 1; 6; 5; 4) i = 1; j = 4; (2; 3; 1; 5; 6; 4) i = 1; j = 5; (2; 3; 1; 5; 4; 6) i = 2; j = 1; (2; 3; 1; 5; 4; 6) i = 2; j = 2; (2; 1; 3; 5; 4; 6) i = 2; j = 3; (2; 1; 3; 5; 4; 6) i = 2; j = 4; (2; 1; 3; 4; 5; 6) i = 3; j = 1; (1; 2; 3; 4; 5; 6) i = 3; j = 2; (1; 2; 3; 4; 5; 6) i = 3; j = 3; (1; 2; 3; 4; 5; 6) i = 4; j = 1; (1; 2; 3; 4; 5; 6) i = 4; j = 2; (1; 2; 3; 4; 5; 6) i = 5; j = 1; (1; 2; 3; 4; 5; 6)