Koofers

Past Exam for CMSC 250 - Discrete Structures with Perlis at Maryland (UMD)

Exam Information

Material Type:Exam 2
Professor:Perlis
Class:CMSC 250 - Discrete Structures
Subject:Computer Science
University:University of Maryland
Term:Fall 2009
Keywords:
  • Combinations
  • Infinite Sets
  • Propositional
  • Transitivity
  • Practice Exam
  • Short Answer
  • None of the Above
  • Strong Induction
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

Sample Document Text

SOLUTIONS TO PRACTICE EXAM II 1. Prove by induction for all n ? 1: summationtextni=1 i2i = (n?1)2n+1 + 2 SOLN: base case (n=1):1*2^1 = 2 = (1-1)*2^2 + 2 IH: Suppose the result holds for some n>= 1. Show it also holds for n+1. But Sum(1 to n+1) i2^i = (n+1)2^{n+1} + Sum(1 to n) i2^i = (n+1)2^{n+1} + (n-1)2^{n+1} + 2 (by IH) = n2^{n+1} + 2^{n+1} + n2^{n+1} - 2^{n+1} + 2 = 2n*2^{n+1} + 2 = n2^{n+2} + 2 QED 2. Let tn = 2tn?1 ?tn?2 for n > 2 where t1 = 1 and t2 = 2. We guess that the sequence satisfies this formula: tn = an2 + bn + c, for some (unknown) constants a,b,c. Use constructive induction to derive values for the constants a,b,c while proving the formula at the same time. Make sure to use the base cases. SOLN: Base cases (n=1,2): t_1 = 1 = a1^2+b*1+c [so need a+b+c=1] t_2 = 2 = a2^2+b*2+c [so need 4a+2b+c=2] IH: t_k = ak^2 + bk + c for 1<=k<=n [or 1 <= k < n and then show for n instead of n+1) Show t_{n+1} = a{n+1}^2 + b{n+1} + c But t_{n+1} = 2t_n - t_{n-1} = 2[an^2 + bn + c] - [a{n...

Related Documents

Combinations Exam
Cmsc 250 Quiz Quiz
Inductive Step Notes
Inductive Step Notes
Inductive Step Notes
155, "/var/app/current/tmp/"