An overview of sequences and summations, both of which provide theoretical support for counting problems in computer science.

Sequences And Summations: Lesson

An arithmetic sequence (sometimes called a "progression") is a particular type of sequence that has an initial value, as with all sequences. A proper arithmetic sequence has a common difference, that when added to the initial number and each consecutive number, provides the arithmetic sequence.  Keep in mind that this common difference can be a positive or a negative value so the arithmetic sequence might be increasing or decreasing regularly.  In addition, an arithmetic sequence may begin with a negative number as long as the sequence progresses by the constant value from that starting point. 

An arithmetic sequence example would look like this:

1, 5, 9, 13, 17, 21, 25, 29, ... with a common difference of 4.

Look for the common difference by subtracting the preceding value from the current value and ensuring this holds for the following numbers.

Arithmetic Sequences

We use summation rules to simplify our work. Read summation rules carefully; otherwise, it sounds like double talk! Note that we consistently use *k* as the symbol for a constant.

Rule 1: The summation of the sums of two or more variables equals the sum of their summations

```tex
\sum\limits_{i=1}^n(x_{i}+y_{i})=\sum\limits_{i=1}^nx_{i} + \sum\limits_{i=1}^ny_{i}
```

Rule 2: The summation of the product of a constant and the values of a variable is equal to the product of the constant and the summation of the variable

```tex
\sum\limits_{i=1}^nki=k\sum\limits_{i=1}^ni
```

Rule 3: The summation of a constant taken N times is the product of the constant and N                

```tex
\sum\limits_{i=1}^nk=kn
```

Rule 4: The summation of a constant plus the values of a variable is equal to the product of N and the constant, plus the summation of the values of the variable

```tex
\sum\limits_{i=1}^n(k+i)=nk + \sum\limits_{i=1}^ni
```


Rule 5: The summation of the values of a variable minus a constant is equal to the summation of the values of the variable minus the product of N and the constant

```tex
\sum\limits_{i=1}^n(i-k)=\sum\limits_{i=1}^ni-nk
```

Summation Rules

Summation notation is a method for providing a compact description of a summation. Summations start somewhere specific and either terminate definitively (finite) or continue without bounds (infinite). Summations often have terms called “variables," and may also have constants. Summations that only compute *part* of a sequence are called "partial sums." For example:

```tex
\sum\limits_{i=1}^{n}5i
```

If we limit *n* to 5, then we have 

```tex
\sum\limits_{i=1}^{5}5i=5+10+15+20+25=75
```

We already saw that the inverse factorial yields an approximation to *e*.

```tex
\sum\limits_{i=0}^{n}\frac{1}{n!}\approx e
```

Although we have a summation formula, e will be valid to only the fourth decimal place, even with n = 100,000.

Summation Notation

We see sequences every day. A simple example is the flow of events over time. In mathematics and computer science, a sequence is a list of numbers. Particularly, a sequence of numbers must always be ordered. In most cases, we order from the smallest to the largest, but the order can also be decreasing (as long as the entire sequence is decreasing). A sequence of numbers may be finite or infinite. In programming settings, if we have no decisions and no repetition, the list of code instructions would be a sequence in itself. For example, in Python 3:

```py
x = 3
print(x)
```
we see a two-step sequence. An ordered checklist also is a sequence too.


Defining A Sequence

Short finite summations, or partial sums, are common in computer science. For example, one of the most common uses occurs with loop counters. Here is a Python example:

```py
i = 0
while i < 10:
  i = i + 1
  print(i)
```

The `while` loop will not stop unless we sum up the value of "i" and test that value. Please note in this particular example, the symbolism in mathematics looks like this:

```tex
\sum\limits_{i=1}^{10}k
```

where k = 1. Our `while` loop test value is *nk = 10*. Also, notice that the value "10" at the top of the summation symbol tells us we have a finite summation.

With some problems, the value of *n* may be so gigantic as to be costly to calculate. This condition is often called "uncountably finite."

Finite Summations

Moving past sequences, we now look at summations. A summation, as the name implies, is the addition of a sequence of numbers.

As discussed earlier, sequences are ordered. Summations, which add up the terms of a sequence are also ordered; however, they use a special notation to create a shorthand description. Example:

```tex
\sum\limits_{i=1}^{n}i
```

Where *i = 1* is the initial value, *n* is the terminal or "stop" value, and *i* by itself is the description of a single element of the sequence we will sum. Suppose the value given for *n* is not a number, but infinity, in that case we see an infinite series.  Sometimes an infinite series will converge to a target value, such as the example of the natural root *e* we saw earlier. Note that we are not always this fortunate with summations, in many cases an infinite series summation will be infinity.


Summations

This famous arithmetic sequence (progression) problem was supposedly solved by the mathematician Gauss in his childhood. In essence, one solution involves starting at the center of the 100 numbers and adding the two terms (e.g., 50 + 51), and then spreading out in both directions. The learner soon realizes that each pair is equal to 101 and that there are 50 pairs. In general, forms like this one are challenging to discover. An infinite arithmetic progression grows without bounds. A finite arithmetic progression can sometimes be represented by an alternate form that simplifies the calculation. For example, the Gauss approach could be written as:

```tex
(number\ of\ pairs)\cdot(sum\ of\ each\ pair) = \frac{n}{2}(n +1)
```

The algebraic portion after the "=" sign is called a "closed-form." The discovery of closed forms is nontrivial and outside our scope in this lesson.

Simply put, the sum of the first one hundred values looks like this:

```tex
\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}=\frac{100(101)}{2}=5050
```

We can always sum an arithmetic sequence using the summation notation and working through the arithmetic.

Arithmetic Sequence Sum

A finite sequence is exactly what it sounds like - an ordered list of numbers that is finite, meaning it has a stopping value. An extensive finite sequence also has a stopping value, but it is generally too cumbersome to be practical.

An infinite sequence is an ordered list of numbers, the count of which has no stopping value. Some infinite sequences converge to a desired value and provide an estimation of that value. The sequence of factorials starts with 0!, 1!, 2!, 3!, 4!,... and evaluates to: 1, 1, 2, 6, 24, ... 
However, if we sum up the inverses of the sequence of factorials we get this: 


```tex
\frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + ... \approx e
```

where *e* is the natural root = 2.71828... of natural logarithms. The three dots "..." mean the number has no end.

Finite And Infinite Sequences

Much like the arithmetic sequence, a geometric sequence has an initial term. However, a geometric sequence has a common ratio that yields the following number in the geometric sequence when multiplied times the previous number. For example, a geometric sequence with the common ratio of "4" would start like this: 1, 4, 16, 64, 256, …. Geometric sequences grow by multiplication. Geometric expansion is the most common mathematical model for epidemics because of its rapid growth. As with the arithmetic sequence, a geometric sequence may start with a negative initial value.

You find the common ratio, if one exists, by dividing this term by the preceding number and then verifying that this behavior is consecutive. In the example in the previous paragraph, we would divide 16 by 4, yielding 4. We would divide 64 by 16, producing 4. As we continue, we verify that the common ratio in this sequence is "4."