## Introduction

Let

```
Sₙ=∑ { k log₂ k ∣ 2 ≤ k ≤ n-1 }
```

Our overall goal is to prove that for `n≥2`

```
Sₙ ≤ Bₙ ≡ ½ n² log₂ n - ⅛ n²
```

(from the analysis of randomized quicksort). The proof has been broken into several steps. The bound in each question may be used in following steps, whether or not you manage to prove it.

See also the general rules about assignments in this course.

**DUE**: 2018-01-31, 09:15 in the assignment box.

## Questions

Define the

`n`

th harmonic number`Hₙ = ∑ { (1/i) ∣ 1 ≤ i ≤ n}`

. Prove that`Hₙ ≤ ln n + 1`

. Hint: calculus.Prove that

`log₂(n) - log₂(n-1) ≥ 1/(2n)`

for`n≥2`

Prove that

`½(n²-1) log₂ (n-1) - ⅛(n-1)² ≤ Bₙ`

for`n≥2`

Prove by induction that

`Sₙ ≤ Bₙ`

for`n≥2`