Maggie Johnson Handout #26

CS103A

Sequences and Summations

Key topics:

• Sequences
• Summation & Product Notation
• Geometric Series

A mathematician, like a poet or a painter, is a maker of patterns.

G.H. Hardy

A Mathematician’s Apology (1940)

Sequences

Imagine a person (with a lot of time on their hands) that decides to count their ancestors. She has two parents, four grandparents, eight great-grandparents, and so forth. We could write these numbers in a row: 2, 4, 8, 16, 32, 64, … (where the … means and so forth).

To express a pattern of numbers in this manner, we often label the position of each number in the row as in the following table.

1	2	3	4	5	6
2	4	8	16	32	64

When represented in this manner it is easy to recognize a formula that would give us the kth element in the row: A_k = 2^k. Note that we are just making an observation based on evidence in guessing this formula. We would need to do a proof to be absolutely certain.

A sequence is an ordered list of elements written in a row, such that each element has a unique position in the list. We use a_k to denote a single element of a sequence called a term. The k in a_k is called a subscript or index. An explicit formula for a sequence is a rule that shows how the value of a_k is derived from k.

What is the programming analogy of a sequence?

A common problem in computer science is determining an explicit formula given only the first few elements of a sequence. When trying to find such a formula we try to find a pattern. According to Rosen, a good place to start is in asking the following questions:

• Are there runs of the same values?
• Are terms obtained from previous terms by adding the same amount, or an amount that depends on position in the sequence?
• Are terms obtained from previous terms by multiplying by a particular amount?
• Are terms obtained by combining previous terms in a certain way?

Here are some practice problems:

1) 3, 6, 11, 18, 27, 38, 51, 66, 83

2) 7, 11, 15, 19, 23, 27, 31, 35…

3) 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011…

4) 0, 2, 8, 26, 80, 242, 728, 2186, 6560, 19682…

Summation & Product Notation

Going back to our original question of counting ancestors, suppose we want to know the total number of ancestors for the past six generations. There is a convenient shorthand notation to write such sums. In 1772, the French mathematician Joseph Lagrange introduced the capital Greek letter sigma Σ to denote the word “sum”.

n

∑ a_k

k=1 represents a1 + a2 + a3 + … + an

k is called the index of summation which starts with the lower limit 1, and ends with the upper limit n.

What is the value of the following?

5

∑ j²

j=1

The notation for the product of a sequence of numbers is analogous to the notation for their sum, except we use the capital Greek letter pi, ∏ to denote a product:

n

∏ a_k

k=1 represents a1 * a2 * a3 * … * an

Geometric Series

A geometric progression is a sequence of the form

a, ar, ar², ar³, …, ar^k

Where a, the initial term and r, the common ratio are real numbers. Sums of geometric progressions are very common in discrete math and computer science. Such sums are called geometric series. There is a well-known and useful formula for the sum, S, of the first n terms of a geometric series.

S = (arⁿ⁺¹ – a) / (r – 1)

How is this formula derived?

What is the value of the following?

4 3

∑ ∑ ij

i=1 j=1