Summation

1.2.6 Summation

Series

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

∑n ak k=1

(1.2.10)

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

Given a sequence a₁,a₂…, the infinite sum a₁ + a₂ + … can be written

∑∞ ∑n ak ⇒ nli→m∞ ak k=1 k=1

(1.2.11)

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.

Linearity

For any real number c and any finite sequence a₁,a₂,…a_n and b₁,b₂,…b_n,

n∑ n∑ ∑n (c⋅ak + bk) = c ⋅ (ak)+ (bk) (1.2.12) k=1 k=1 k=1

The linearity property can be exploited to manipulate summations incorporating asymptotic notation.[1]

n n ∑ Θ (f(k )) = Θ ∑ (f(k )) (1.2.13) k=1 k=1

Arithmetic Series

Here are some common arithmetic series and their tight bounds:

∑n 1 2 (k) = 1 + ...+ n = 2 ⋅n⋅(n+ 1) = Θ(n ) k=n1 ∑ 2 1 3 (k ) = 6 ⋅n ⋅(n + 1)⋅(2n+ 1) = Θ (n ) k=n1 ∑ (k3) = 1 ⋅n2 ⋅(n + 1)2 = Θ(n4) (1.2.14) k=1 4

Geometric Series

For a real number, x≠1, the geometric series (or exponential series) is defined as follow:

∑n k xn+1---1 ∀x ∈ R,x ⁄= 1,n → ∞, (x ) = x- 1 (1.2.15) k=0

When this summation goes to infinite, and |x| < 1, we then have a decreasing geometric series.

∑n 1 ∀|x| < 1,n → ∞, (xk) = 1---x (1.2.16) k=0

Differentiation

For any real number, k,

∑n k --1-- (x ) = 1- x k=0 n ⇒ ∑ (k ⋅xk- 1) =---1--- k=0 (1- x)2 ∑n ⇒ (k ⋅xk) =---x--- (1.2.17) k=0 (1- x)2

Harmonic Series

For positive integer n, the n_th harmonic number is

Hn = 1 + 1+ 1+ 1 + ...+ 1- n 2 3 4 n ∑ 1- = (k) k=1 = lgn = Θ(lgn) (1.2.18)

Telescoping Series

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

∑n (ak - ak-1) = (a1 - a0) +(a2 - a1)+ ...+ (an - an-1) k=1 = an - a0 n∑-1 (ak - ak+1) = a0 - an (1.2.19) k=0

Polynomials

Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form,

∑d p(n ) = (ai ⋅ni) (1.2.20) i=0

, where the constants a₀,a₁…a_d are the coefficients of the polynomial and a_d≠0. For any real constant a ≥ 0, the function n^a is monotonically increasing, and for any real constant a ≤ 0, the function n^a is monotonically decreasing.[1]
A function is said to be polynomially bounded if f(n) = O(n^k) for some constant k. [1]

Products

The finite product a₁ ⋅ a₂ ⋅… ⋅ a_n can be written

∏n ak k=1

(1.2.21)

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.[1]

∏n ∑n lg( ak) = lg(ak) (1.2.22) k=1 k=1

[next] [prev] [prev-tail] [front] [up]