Mathematical Preliminaries for COMP372 Algorithms

Summations are the sum for some function over a range of parameter values. An example of a summation is to analyze running time costs for programs with loops, in which we need to add up the costs for each time the loop is executed. Summations are typically written with the following "sigma" notation: \( \sum\limits_{i = 1}^n {f(i)} \) This notation indicates that we are summing the value of \(f(i)\) as \(i\) ranges from 1 through \(n\). This can alos be written: \( f(1) + f(2) + ... + f(n-1) + f(n) \) The following is a list of useful summations for data structure and algorithm analysis:
\( \sum\limits_{i = 1}^n {i} = \frac{n(n+1)}{2}\)
\( \sum\limits_{i = 1}^n {i^2} = \frac{2n^3 + 3n^2+n}{6}\)
\( \sum\limits_{i = 1}^{log(n)} {n} = n log n\)
The sum of an infinite geometric series:
\( \sum\limits_{i = 0}^\infty {a^i} = \frac{1}{1-a} \), for -1 < a < 1 (1)
As special cases to equcation (1):
\( \sum\limits_{i = 0}^{n} {2^i} = 1- \frac{1}{2^n} \)
and
\( \sum\limits_{i = 0}^{n} {a^i} = \frac{a^{n+1}-1}{1-a} \), for a > 1 (2)
In another variation, \( \sum\limits_{i = 1}^{n} \frac{i}{2^i} = 2- \frac{n+2}{2^n} \)
As a special case to Equcation (2),
\( \sum\limits_{i =1}^{n} {2^i} = 2^{n+1} - 1 \) (3)
As a corollary to Equcation (3),
\( \sum\limits_{i =0}^{log n} {2^i} = 2^{log n+1} - 1 \)

1. \(2^1+2^2+...+2^n = \)

\( 2(2^n -1) \) \( 2(2^{n-1}-1) \) \( 2(2^{n+1}-1) \) None of the above

2. The sum of an infinite geometric series exists only if the condition on the common ratio a

\( a \geq -1, a \leq 1 \) \( -1 \leq a \leq 1 \) \( a>-1, a<1 \) \( -1 < a < 1 \)

3. Find the sum of the geometric series \( \sum\limits_{i=0}^\infty {{(-\frac{1}{3})}^i} \)

1 4 0.5 0.75

4. Which of the following is the first four terms of the sequence whose general term is given \( a_n = 3^n, n = 1, 2, ...\)

9, 27, 81, 243 1. 4, 9, 16 1, 3, 6, 9 3, 9, 27, 81 Submit

Your grade is: __