1.5. Summations¶

1.5.1. Summations¶

Most programs contain loop constructs. When analyzing running time costs for programs with loops, we need to add up the costs for each time the loop is executed. This is an example of a summation. Summations are simply the sum of costs for some function applied to a range of parameter values. Summations are typically written with the following "Sigma" notation:

\[\sum_{i=1}^{n} f(i).\]

This notation indicates that we are summing the value of \(f(i)\) over some range of (integer) values. The parameter to the expression and its initial value are indicated below the \(\sum\) symbol. Here, the notation \(i=1\) indicates that the parameter is \(i\) and that it begins with the value 1. At the top of the \(\sum\) symbol is the expression \(n\). This indicates the maximum value for the parameter \(i\). Thus, this notation means to sum the values of \(f(i)\) as \(i\) ranges across the integers from 1 through \(n\). This can also be written \(f(1) + f(2) + \cdots + f(n-1) + f(n)\). Within a sentence, Sigma notation is typeset as \(\sum_{i=1}^{n} f(i)\).

Given a summation, you often wish to replace it with an algebraic equation with the same value as the summation. This is known as a closed-form solution, and the process of replacing the summation with its closed-form solution is known as solving the summation. For example, the summation \(\sum_{i=1}^{n} 1\) is simply the expression "1" summed \(n\) times (remember that \(i\) ranges from 1 to \(n\)). Because the sum of \(n\) 1s is \(n\), the closed-form solution is \(n\).

Here is an explanation about the closed form solution of one summation that you will see many times in this book. Since this appears so often, it will help you later if you can get comfortable with it.

Settings

Saving...

Server Error
Resubmit

Settings

Saving...

Server Error
Resubmit

Here is a list of useful summations, along with their closed-form solutions.

\[\begin{split}\sum_{i = 1}^{n} i &=& \frac{n (n+1)}{2}.\end{split}\]

\[\begin{split}\sum_{i = 1}^{n} i^2 &=& \frac{2 n^3 + 3 n^2 + n}{6} = \frac{n(2n + 1)(n + 1)}{6}.\end{split}\]

\[\begin{split}\sum_{i = 1}^{\log n} n &=& n \log n.\end{split}\]

\[\begin{split}\sum_{i = 0}^\infty a^i &=& \frac{1}{1-a}\ \mbox{for} \ 0 < a < 1.\end{split}\]

\[\begin{split}\sum_{i=0}^{n} a^i &=& \frac{a^{n+1} - 1}{a - 1}\ \mbox{for} \ a \neq 1.\end{split}\]

As special cases to this last summation, we have the following two:

\[\begin{split}\sum_{i = 1}^{n} \frac{1}{2^i} &=& 1 - \frac{1}{2^n},\end{split}\]

\[\begin{split}\sum_{i = 0}^{n} 2^i &=& 2^{n+1} - 1.\end{split}\]

As a corollary to (?),

\[\begin{split}\sum_{i = 0}^{\log n} 2^i &=& 2^{\log n + 1} - 1 = 2n - 1.\end{split}\]

Finally,

\[\begin{split}\sum_{i=1}^{n} \frac{i}{2^i} &=& 2 - \frac{n+2}{2^n}.\end{split}\]

The sum of reciprocals from 1 to \(n\), called the Harmonic Series and written \({\cal H}_n\), has a value between \(\log_e n\) and \(\log_e n + 1\). To be more precise, as \(n\) grows, the summation grows closer to

\[{\cal H}_n \approx \log_e n + \gamma + \frac{1}{2n},\]

where \(\gamma\) is Euler's constant and has the value 0.5772...

Most of these equalities can be proved easily by a proof by induction. Unfortunately, induction does not help us derive a closed-form solution. Induction only confirms when a proposed closed-form solution is correct.

Data Structures and Algorithms Y

Chapter 1 Mathematical Background

1.5. Summations¶

1.5.1. Summations¶