# 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: CombinationsInfinite SetsPropositionalTransitivityPractice ExamShort AnswerNone of the AboveStrong Induction      ## 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