Summations

Here is a very interesting summation formula that generalizes many familiar ones:

$$\sum_{i=1}^n i(i+1)\ldots (i+s) = \frac{n(n+1)\ldots (n+s+1)}{s+2}$$

It can be proven by induction; we will not do this here.

Another standard summation formula is for the geometric series, for $x \neq 1$:

$$\sum_{i=0}^n x^i = 1+x+\ldots+x^n = \frac{x^{n+1}-1}{x-1}$$

which is very easy to prove by elementary algebraic manipulation. When the upper limit $n$ is $\infty$ and when $\vert x\vert < 1$, this gives

$$\sum_{i=0}^{\infty} x^i = 1/(1-x)$$

By differentiating, we can get yet another summation formula

$$\sum_{i=0}^{\infty} ix^{i-1} = 1/(1-x)^2$$

and then by multiplying through by $x$, yet another:

$$\sum_{i=0}^{\infty} ix^{i} = x/(1-x)^2$$

However, sometimes summations cannot be reduced exactly to a familiar compact formula. In such cases we may use approximations instead. Here is a simple example using the method called bounding:

$$1 \leq \sum_{i=1}^n 1/i \leq n$$

This summation is a famous one, called the harmonic series and we have encountered it before in the average case runtime for insertion sort, but we did not know then how to approximate it.

So, how do use bounding to see that the sum lies between the two limits given? Well, every term is at least as large as the smallest, $1/n$ and there are $n$ terms, so if we replaced them all by the smallest, the sum would be only $n \times i/n = 1$. Also $1$ is the largest term, and so replacing all the terms by the largest--which gives $n \times 1 = n$--can only increase the result.

On the other hand, this is a very crude approximation, and does not tell us very much about how big the sum is. Instead of replacing all terms by the least term, we could have simply taken the first two terms of the sum ($1/1$ and $1/2$) and since there are no negative terms, the sum must be at least as large as the sum of the first two, giving a lower limit of $1.5$, a slight improvement. Or, instead of the first two terms, we could use, say, the first ten, on the left, getting an even better lower bound. But a more sophisticated method is that of first splitting:

$$S = \sum_{i=1}^n 1/i = \sum_{i=1}^{n/2} 1/i + \sum_{i={n/2+1}}^n 1/i$$

(supposing $n$ to be even) and then bounding each of these new sums by replacing all their terms by the smallest (and then the largest) values:

$$\frac{1}{n/2}\times n/2 + \frac{1}{n} \times n/2 \leq S \leq 1 \times n/2 + (n/2+1) \times n/2$$

and so

$$1 + 1/2 \leq S \leq n/2 + n/(n+2)$$

The LHS has not gotten any better than before, it is still $1.5$. But at least the RHS has dropped down a lot, and for large $n$ it is essentially just $n/2$. For the particular sum in this example, an even better method exists, that we will see soon. However, splitting and bounding, used together, often are fairly good, as the next example shows (again where we assume $n$ is even for simplicity):

$$S = \sum_{i=1}^n i^2 = \sum_{i=1}^{\frac{n}{2}} i^2 + \sum_{i={\frac{n}{2}+1}}^n i^2$$

$$1^2 \times n/2 + (\frac{n}{2}+1)^2 \times n/2 \leq S \leq (\frac{n}{2})^2 \times n/2 + n^2 \times n/2$$

$$n/2 + (n/2 + 1)^2 n/2 \leq S \leq (n/2)^3 + n^3 /2$$

and so

$$n^3/8 \leq S \leq 5n^3/8$$

Thus $S =\Theta(n^3)$, and for example if $n=20$ we have

$$20^3/8 \leq S = \sum_{i=1}^{20} i^2 \leq 5\times 20^3 /8$$

$$1000 \leq S \leq 5000$$

This still it does not pin the sum down very tightly; we will soon see a stronger method. But sometimes even the weaker method is enough; for instance, if we need to know whether the above sum to 20 is greater than, say, 500, then we have the answer. And we also were able to show that the general sum to $n$ is $\Theta(n^3)$.

Sometimes, for very special summations, the following ratio method variation on bounding works well:

Let $S = \sum_{i=1}^n a_n$ be a series of positive terms and suppose there is a constant $r$ such that $\frac{a_{i+1}}{a_i} \leq r < 1$ for all $i$. Then

$$\sum_{i=1}^n a_i \leq \sum_{i=0}^{\infty} a_1 r^i = a_1 \sum_{i=0}^{\infty} r^i = a_1 \frac{1}{1-r}$$

Here is an example: $\sum_{i=1}^{\infty} i/3^i$ where $a_i = i/3^i$, and we compute the ratio $a_{i+1}/a_i = (1+1)/3i \leq 2/3 < 1$. So we choose $r=2/3$ and then $\sum_{i=1}^{\infty} \leq \frac{1}{3} \cdot \frac{1}{1-\frac{2}{3}} = 1$.

Now we turn to the integral method for approximating summations. Consider the sum $\sum_{i=a}^{b} f(i)$ where $f(x)$ is a function of a real variable $x$. There are two standard cases:

1. The function $f$ is increasing on the interval $[a-1,b+1]$. Then we have
   $$\int_{a-1}^b f(x)dx \leq \sum_{i=a}^{b} f(i) \leq \int_{a}^{b+1} f(x)dx$$

2. The function $f$ is decreasing on the interval $[a-1,b+1]$. Then
   $$\int_{a}^{b+1} f(x)dx \leq \sum_{i=a}^{b} f(i) \leq \int_{a-1}^{b} f(x)dx$$

The harmonic series is a good one to use here: since $1/i$ is a decreasing function, then we get:

$$\int_{1}^{n+1} 1/x dx \leq \sum_{i=1}^{n} 1/i \leq \int_{0}^{n} 1/x dx$$

However, the integral on the right is not well-defined, since $1/x$ is unbounded at 0. We can get around this by splitting off the first term in the sum:

$$\int_{1}^{n+1} 1/x dx \leq S = \sum_{i=1}^{n} 1/i \leq 1 + \int_{1}^{n} 1/x dx$$

$$\ln(x)\vert _{1}^{n+1} \leq S \leq 1 + \ln(x)\vert _{1}^{n}$$

$$\ln(n+1) \leq S \leq 1 + \ln{n}$$

Products have a notation analogous to summations:

$$\Pi_{i=1}^{n} a_i = a_1a_2\ldots a_n$$

and because of the familiar fact about the logarithm of a product, we have

$$\lg \Pi_{i=1}^{n} a_i = \sum_{i=1}^{n} \lg a_i$$