Self-Assessment Quiz: Sequences and Summations

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Throughout, recall the book's conventions: the upper limit of a sum is inclusive, an empty sum is $0$, and an empty product is $1$.

Question 1

A closed form for a sequence is best described as:

A) a rule that gives term $n$ directly from $n$, without computing earlier terms B) a rule that gives term $n$ from term $n-1$ C) the first few terms listed explicitly D) the sum of all the terms

Question 2

How many terms are in the sum $\sum_{i=4}^{20} a_i$?

A) 16 B) 17 C) 20 D) 24

Question 3

The faithful Python translation of $\sum_{i=m}^{n} a_i$ is:

A) sum(a(i) for i in range(m, n)) B) sum(a(i) for i in range(m, n + 1)) C) sum(a(i) for i in range(m - 1, n)) D) sum(a(i) for i in range(m + 1, n + 1))

Question 4

Which equation is correct?

A) $\sum_{i=1}^{n} (3i + 2) = 3\sum_{i=1}^{n} i + 2$ B) $\sum_{i=1}^{n} (3i + 2) = 3\sum_{i=1}^{n} i + 2n$ C) $\sum_{i=1}^{n} (3i + 2) = 3\sum_{i=1}^{n} i + n$ D) $\sum_{i=1}^{n} (3i + 2) = 3n\sum_{i=1}^{n} i + 2n$

Question 5

The arithmetic-series formula $\sum_{i=0}^{n-1}(a + id)$ can be remembered as:

A) the first term times the number of terms B) the number of terms times the average of the first and last terms C) the last term times the common difference D) the sum of the first and last terms, divided by 2

Question 6

The "schoolboy Gauss" trick that derives the arithmetic-series formula is:

A) multiply the sum by the common difference and subtract B) write the sum forwards and backwards, then add the two columns C) split the summand by partial fractions D) prove it by induction

Question 7

The key move that derives the geometric-series formula is:

A) write the sum forwards and backwards, then add B) multiply the whole sum by the ratio $r$, then subtract C) integrate term by term D) take the limit as $n \to \infty$

Question 8

$\displaystyle\sum_{i=0}^{n-1} 2^i$ equals:

A) $2^n$ B) $2^n - 1$ C) $2^{n-1}$ D) $n^2$

Question 9 (True/False, justify)

True or false: The infinite series $\sum_{i=0}^{\infty} a r^i$ converges to $\frac{a}{1-r}$ for every real ratio $r$. Justify in one sentence.

Question 10

A telescoping sum is one whose summand can be written as:

A) a product of consecutive terms B) a difference of consecutive values of some sequence, $t_i - t_{i-1}$ C) a constant times the index D) a power of two

Question 11

$\displaystyle\sum_{i=1}^{n} (t_i - t_{i-1})$ collapses to:

A) $t_n + t_0$ B) $t_n - t_0$ C) $t_0 - t_n$ D) $n(t_n - t_0)$

Question 12

The harmonic number $H_n = \sum_{i=1}^{n} \frac{1}{i}$:

A) has the closed form $\frac{n(n+1)}{2}$ B) has no elementary closed form and grows like $\ln n$, i.e. $\Theta(\log n)$ C) converges to a finite limit as $n \to \infty$ D) equals $2^n - 1$

Question 13 (True/False, justify)

True or false: $0! = 0$. Justify in one sentence.

Question 14

An empty product $\prod_{i=3}^{2} a_i$ equals:

A) $0$ B) $1$ C) undefined D) $a_2$

Question 15

In the growth hierarchy, where does $n!$ sit relative to $2^n$ and $n^n$?

A) $n^n \prec n! \prec 2^n$ B) $2^n \prec n! \prec n^n$ C) $n! \prec 2^n \prec n^n$ D) $2^n \prec n^n \prec n!$

Question 16

The double loop for i in range(n): for j in range(i + 1, n): steps += 1 runs steps += 1 a total of:

A) $n^2$ times B) $\frac{n(n+1)}{2}$ times C) $\frac{n(n-1)}{2}$ times D) $n \log_2 n$ times

Question 17 (True/False, justify)

True or false: A loop whose counter doubles, i = 1; while i < n: i *= 2, runs about $\log_2 n$ times, and if pass number $j$ does $2^j$ units of work, the total work is still less than $2n$. Justify in one sentence.

Question 18

The loop for i in range(n): (a doubling inner loop ~log2(n) passes) has total step count:

A) $\Theta(n^2)$ B) $\Theta(n)$ C) $\Theta(\log n)$ D) $\Theta(n \log n)$

Question 19 (Short answer)

Shift the index of $\sum_{i=2}^{n} a_i$ so that the new index starts at $0$. Write the resulting sum.

Question 20 (Short answer)

In one sentence, explain why turning a slow recurrence into a closed form is valuable for a programmer, using the words "random access" and "sequential access."

Answer Key

Topics to review by question