3.5.1. Summations¶
Most programs contain loop constructs.When analyzing running time costs for programs with loops, weneed 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 arange 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 indicatedbelow 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 algebraicequation 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-formsolution 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 summationthat you will see many times in this book.Since this appears so often, it will help you later if you can getcomfortable 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} \\\sum_{i = 1}^{n} i^2 &= \frac{2 n^3 + 3 n^2 + n}{6} = \frac{n(2n + 1)(n + 1)}{6} \\\sum_{i = 1}^{\log n} n &= n \log n \\\sum_{i = 0}^\infty a^i &= \frac{1}{1-a}\ \text{for} \ 0 < a < 1 \\\sum_{i = 0}^{n} a^i &= \frac{a^{n+1} - 1}{a - 1}\ \text{for} \ a \neq 1 \\\text{As special cases to the last summation, we have the following two:} \\sum_{i = 1}^{n} \frac{1}{2^i} &= 1 - \frac{1}{2^n} \\\sum_{i = 0}^{n} 2^i &= 2^{n+1} - 1 \\\text{As a corollary to the previous summation: } \\sum_{i = 0}^{\log n} 2^i &= 2^{\log n + 1} - 1 = 2n - 1 \\\text{Finally: } \\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 theHarmonic Series and written \({\cal H}_n\), has a valuebetween \(\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 aproof by induction.Unfortunately, induction does not help us derive a closed-formsolution.Induction only confirms when a proposed closed-form solution iscorrect.
