## Exam Information

Login / Sign Up to View Document

## 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

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.