Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources]

A.1 Summation formulas and properties

Given a sequence a₁, a₂, ... of numbers, the finite sum a₁ + a₂ + ··· + a_n, where n is an nonnegative integer, can be written

If n = 0, the value of the summation is defined to be 0. The value of a finite series is always well defined, and its terms can be added in any order.

Given a sequence a₁, a₂, ... of numbers, the infinite sum a₁ + a₂ + ··· can be written

which is interpreted to mean

If the limit does not exist, the series diverges; otherwise, it converges. The terms of a convergent series cannot always be added in any order. We can, however, rearrange the terms of an absolutely convergent series, that is, a series for which the series also converges.

Linearity

For any real number c and any finite sequences a₁, a₂, ..., a_n and b₁, b₂, ..., b_n,

The linearity property is also obeyed by infinite convergent series.

The linearity property can be exploited to manipulate summations incorporating asymptotic notation. For example,

In this equation, the Θ-notation on the left-hand side applies to the variable k, but on the right-hand side, it applies to n. Such manipulations can also be applied to infinite convergent series.

Arithmetic series

The summation

is an arithmetic series and has the value

Sums of squares and cubes

We have the following summations of squares and cubes:

Geometric series

For real x ≠ 1, the summation

is a geometric or exponential series and has the value

When the summation is infinite and |x| < 1, we have the infinite decreasing geometric series

Harmonic series

For positive integers n, the nth harmonic number is

(We shall prove this bound in Section A.2.)

Integrating and differentiating series

Additional formulas can be obtained by integrating or differentiating the formulas above. For example, by differentiating both sides of the infinite geometric series (A.6) and multiplying by x, we get

for |x| < 1.

Telescoping series

For any sequence a₀, a₁, ..., a_n,

since each of the terms a₁, a₂, ..., a_n-1 is added in exactly once and subtracted out exactly once. We say that the sum telescopes. Similarly,

As an example of a telescoping sum, consider the series

Since we can rewrite each term as

we get

Products

The finite product a₁ a₂ · · a_n can be written

If n = 0, the value of the product is defined to be 1. We can convert a formula with a product to a formula with a summation by using the identity

Exercises A.1-1

Find a simple formula for

Exercises A.1-2: ⋆

Show that by manipulating the harmonic series.

Exercises A.1-3

Show that for 0 < |x| < 1.

Exercises A.1-4: ⋆

Show that .

Exercises A.1-5: ⋆

Evaluate the sum .

Exercises A.1-6

Prove that by using the linearity property of summations.

Exercises A.1-7

Evaluate the product .

Exercises A.1-8: ⋆

Evaluate the product .