Hwk0-sol - cmsc351 PDF

Preview

Summary

cmsc351...

Description

CMSC351 (Kruskal)

Homework 0

Due: Friday, August 30, 2019

There are eight problems. Within reason, you should show your work.

Problem 1. Evaluate the following sums (by hand). (a) 4 X

i(i + 1)

i=1

Solution: 1 · 2 + 2 · 3 + 3 · 4 + 4 · 5 = 2 + 6 + 12 + 20 = 40 (b) 4 X

2i

i=0

Solution: 20 + 21 + 22 + 23 + 24 = 1 + 2 + 4 + 8 + 16 = 31

Problem 2. Write 3

n X

2

(5i − 4) − 2

Solution:

(3i2 − 1)

i=1

i=1

as a single summation.

n X

n X

(9i2 − 10)

i=1

Problem 3. Use mathematical induction to show the following: (a)

n X

i=1

i(i + 1) =

n(n + 1)(n + 2) 3

CMSC351 (Kruskal)

Homework 0

Due: Friday, August 30, 2019

Solution: Base case: (n = 1): The value of the summation is 1 X

i(i + 1) = 1(1 + 1) = 2 .

i=1

The formula gives 1(1 + 1)(1 + 2) =2 . 3 Since these are equal we have proved the base case. Induction step: Assume the formula holds for n − 1. This implies that n−1 X

i(i + 1) =

i=1

(n − 1)n(n + 1) . 3

Thus, n X

i(i + 1) =

i=1

n−1 X

i(i + 1) + n(n + 1)

i=1

= = = =

 (n − 1)n(n + 1) + n(n + 1) 3 3n(n + 1) (n − 1)n(n + 1) + 3 3 (n + 2)n(n + 1) 3 n(n + 1)(n + 2) 3



by the induction hypothesis

This is the desired formula. (b)

n X

2i = 2n+1 − 1

i=0

Solution: Base case: (n = 0): The value of the summation is 0 X

2i = 20 = 1 .

i=0

The formula gives

20+1 − 1 = 2 − 1 = 1 . Induction step: Assume the formula holds for n − 1. This implies that n−1 X

2i = 2n − 1.

i=0

Page 2 of 6

CMSC351 (Kruskal)

Homework 0

Due: Friday, August 30, 2019

Thus, n X

2

i

n−1 X

=

2i

i=0

i=0

!

+ 2n

= (2n − 1) + 2n

by the induction hypothesis

n

= 2·2 −1 = 2n+1 − 1

Problem 4.

Assume that you guess that n X

2i = a2n + b

i=0

for constants a and b. Use constructive induction to verify the formula and derive a and b. Solution: Base case: (n = 0): The value of the summation is 1 (as above). The formula gives a2n + b = a20 + b = a · 1 + b = a + b. So a + b = 1. Induction step: Assume the formula holds for n − 1. This implies that n−1 X

2i = a2n−1 + b.

i=0

Thus, n X i=0

2

i

=

n−1 X

2

i=0

i

!

+ 2n

= (a2n−1 + b) + 2n by the induction hypothesis a n = ( 2 + b) + 2n 2 a = ( + 1)2n + b 2 = a2n + b to make the induction work

So we need a = a/2 + 1, which implies a = 2. By the base case, a + b = 1, which implies 2 + b = 1. So b = −1. Thus, n X

2i = 2 · 2n − 1 = 2n+1 − 1

i=0

Page 3 of 6

CMSC351 (Kruskal)

Homework 0

Due: Friday, August 30, 2019

Problem 5. (a) Assume bx = a. What is x (in terms of a and b)? Solution: x = logb a. (b) Using only part (a), show that logc (ab) = logc a + logc b. Solution: x = logb a. By part (a), a = clogc a, b = clogc b , and ab = clogc (ab) . So, clogc (ab) = ab = clogc a · clogc b = clogc a+logc b . Since, exponentiation to the same base c 6= 1 is one-to-one, logc (ab) = logc a + logc b. (c) Show that alogb n = nlogb a. Solution: Since the log function is one-to-one, to show that f (n) = g(n), it suffices to show that logb f (n) = logb g(n): logb (alogb n ) = (logb n)(logb a) = (logb a)(logb n) = logb (nlogb a)

Page 4 of 6

CMSC351 (Kruskal)

Homework 0

Due: Friday, August 30, 2019

Problem 6. Differentiate the following functions: (a) ln(x2 + 5) Solution:

(b) lg(x2 + 5)

2x x2 + 5 [NOTE: In Computer Science we use lg x to mean log2 x.]

Solution: lg(x2 + 5) =

ln(x2 +5) ln 2

, so the derivative is (x2

(c)

2x 2x lg e = 2 x +5 + 5) ln 2

1 ln(x2 +5)

Solution:

1 ln(x2 +5)

= (ln(x2 + 5))−1 , so the derivative is

−(ln(x2 + 5))−2

x2

2x 1 2x = − 2 +5 (x + 5)(ln(x2 + 5))2

Problem 7. Integrate the following functions: (a)

1 x

Solution:

(b)

Z

1 dx = ln x + C x

1 7x+3

Solution: Use substitution. Let y = 7x + 3. Then dy = 7dx. So, Z Z 1 dy ln y ln(7x + 3) 1 dx = = +C = +C 7x + 3 7 7 y 7 (c) ln x

[HINT: Use integration by parts.]

Solution: Let u = ln x and dv = dx. Then, du = dx/x and v = x. So, Z Z Z xdx = x ln x − dx = x ln x − x + C ln xdx = x ln x − x

Page 5 of 6

CMSC351 (Kruskal) (d) x ln x

Homework 0

Due: Friday, August 30, 2019

[HINT: Use integration by parts.]

Solution: Let u = ln x and dv = xdx. Then, du = dx/x and v = x2 /2. So, Z Z 2 Z x2 ln x x2 x2 ln x x x x2 − dx = dx/x = ln x − x ln xdx = − +C 2 2 2 2 2 4 (e) x lg x Solution: By part (d) and the fact that x lg x = Z

x lg xdx =

1 ln 2

Z

x ln xdx =

x ln x , ln 2

x2 x2 ln x x2 lg x x2 lg e +C − − +C = 4 2 2 ln 2 4 ln 2

Problem 8. Consider the formula 3n4 + 7n3 log n + 2n2 . (a) What is the high order term? Solution: 3n4 (b) What is the second order term? Solution: 7n3 log n (c) Write the formula in Θ notation (in simplest form). Solution: Θ(n4 )

Page 6 of 6...