Solution Found!

Computer science / Algorithms 1 / Chapter 1 / Problem 1.5

Algorithms | 1st Edition | ISBN: 9780073523408 | Authors: Sanjoy Dasgupta Algorithms, Christos H. Papadimitriou Algorithms, Umesh Vazirani Algorithms

Change Question

Unlike a decreasing geometric series, the sum of the harmonic series 1, 1/2, 1/3, 1/4

Chapter 1, Problem 1.5

(choose chapter or problem)

Get Unlimited Answers

QUESTION:

Unlike a decreasing geometric series, the sum of the harmonic series 1, 1/2, 1/3, 1/4, 1/5, . . . diverges;that is, Xi=11i= .It turns out that, for large n, the sum of the first n terms of this series can be well approximatedasXni=11i ln n + ,where ln is natural logarithm (log base e = 2.718 . . .) and is a particular constant 0.57721 . . ..Show thatXni=11i= (log n).(Hint: To show an upper bound, decrease each denominator to the next power of two. For a lowerbound, increase each denominator to the next power of 2.)

Questions & Answers

QUESTION:

Unlike a decreasing geometric series, the sum of the harmonic series 1, 1/2, 1/3, 1/4, 1/5, . . . diverges;that is, Xi=11i= .It turns out that, for large n, the sum of the first n terms of this series can be well approximatedasXni=11i ln n + ,where ln is natural logarithm (log base e = 2.718 . . .) and is a particular constant 0.57721 . . ..Show thatXni=11i= (log n).(Hint: To show an upper bound, decrease each denominator to the next power of two. For a lowerbound, increase each denominator to the next power of 2.)

ANSWER:

Step 1 of 3

Upper bound:

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 …. + 1/n <= 1 + (1/2 +1/2) + (1/4 + 1/4 + 1/4 + 1/4) + ..

Study Tools You Might Need

Chapter: 12 Problem: 22Q

Introductory Chemistry 5
Is the boiling of water endothermic or exothermic? What is the sign of \(\Delta H\) for the boiling of water? For the condensation of steam? Equation Transcription: Text Transcription: delta H

Chapter: 14 Problem: 71P

Introductory Chemistry 5
Calculate \(\mathrm{[H_3O^+]}\) for each solution. (a) pH = 8.55 (b) pH = 11.23 (c) pH = 2.87 (d) pH = 1.22 Equation Transcription: Text Transcription: [H_3O^+]

Chapter: 4 Problem: 33P

A First Course in Probability 9
Problem 33P A newsboy purchases papers at 10 cents and sells them at 15 cents. However, he is not allowed to return unsold papers. If his daily demand is a binomial random variable with n = 10, p = , approximately how many papers should he purchase so as to maximize his expected profit?

Chapter: 7 Problem: 22E

Stats: Data and Models 4
Problem 22E Car thefts The National Insurance Crime Bureau reports that Honda Accords, Honda Civics, and Toyota Camrys are the cars most frequently reported stolen, while Ford Tauruses, Pontiac Vibes, and Buick LeSabres are stolen least often. Is it reasonable to say that theres a correlation betwee

Chapter: Problem: 7

Myers' Psychology for AP 2
Researchers studying gender have found that a. there are more similarities than differences between the genders. b. there are no significant cognitive differences between the genders. c. there are no significant emotional differences between the genders. d. research tools are not capable of determini

Chapter: 1 Problem: 36

Anatomy & Physiology 1
Identify the four components of a negative feedback loop and explain what would happen if secretion of a body chemical controlled by a negative feedback system became too great.

Chapter: 21 Problem: Questions for Review 21.1

Principles of Economics 6
A consumer has income of $3,000. Wine costs $3 per glass, and cheese costs $6 per pound. Draw the consumers budget constraint. What is the slope of this budget constraint?

Chapter: 5 Problem: 4

Essentials of Understanding Psychology 11
Match the type of operant learning with its definition: a. positively reinforcing. b. negatively reinforcing. 4. In a reinforcement schedule, behavior is a. positive reinforcement b. negative reinforcement c. positive punishment d. negative punishment

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

×

Register

Sign up for access to all content on our site!

Or login if you already have an account