Difficulty: Intermediate | Prerequisites: Geometric series, summation notation (sigma), basic algebra
This material sits in the discrete mathematics core of your CS degree, covering closed-form evaluation of finite and infinite sums and the mechanics of linear recurrence relations. You need fluent summation skills for algorithm analysis (think Big-O derivations) and recurrence relations for understanding recursive algorithms. If you are not comfortable with sigma notation or the formula for a geometric series, review those first.
Finite summations can often be broken into known closed forms (sum of squares, sum of integers) and then simplified. Infinite series with a geometric component converge when |r| < 1, and you can split them into manageable sub-series. Recurrence relations define sequences by referring to earlier terms; you compute new values by substituting backwards until you hit the base cases.
Closed-form expression
A formula that gives the value of a sum or sequence directly in terms of n, without needing to iterate. In simple terms, it is the "answer" you get after collapsing a summation into a single algebraic expression.
Geometric series
A sum of the form ∑ arⁱ. When |r| < 1, the infinite version converges to a/(1 − r). Think of it as the bread-and-butter series that appears whenever a ratio is involved.
Arithmetic-geometric series
A series where each term is the product of an arithmetic factor and a geometric factor, e.g. ∑ i · rⁱ. These require special techniques such as the subtraction method or differentiation of the geometric series formula.
Recurrence relation
A rule that defines each term of a sequence using one or more previous terms, plus base cases. In simple terms, it is a recipe: "to get the next number, combine the earlier numbers this way."
Linear recurrence
A recurrence where each term is a linear combination of previous terms (no squaring, no products of earlier terms). The recurrence g(n) = 2g(n−1) + g(n−2) − 2g(n−3) is linear with constant coefficients.
Split the sum into two standard sums:
∑ i² from 1 to 2ⁿ = 2ⁿ(2ⁿ + 1)(2ⁿ⁺¹ + 1) / 6
∑ i from 1 to 2ⁿ = 2ⁿ(2ⁿ + 1) / 2
Subtract the second from the first and factor. The key move is recognising that both share the factor 2ⁿ(2ⁿ + 1).
After simplification:
∑ (i² − i) = 2ⁿ(2ⁿ + 1)(2ⁿ⁺¹ + 1) / 6 − 2ⁿ(2ⁿ + 1) / 2
= 2ⁿ(2ⁿ + 1)(2ⁿ⁺¹ + 1 − 3) / 6
= 2ⁿ(2ⁿ + 1)(2ⁿ⁺¹ − 2) / 6
= 2ⁿ(2ⁿ + 1) · 2(2ⁿ − 1) / 6
= 2ⁿ(2ⁿ + 1)(2ⁿ − 1) / 3
The required form is 2ᵃ(2ᵇ − 1) / c, so: a = n, b = 2n, c = 3. Equivalently written as 2ⁿ(2²ⁿ − 1) / 3.
Two clean approaches exist.
Approach 1: Subtraction method
Write out S, then (1/3)S, and subtract to cancel terms with matching denominators. After telescoping you reduce the problem to a standard geometric series.
The intermediate result gives (2/3)S = a value you can evaluate, leading to S = 3.
Approach 2: Split into known series
Decompose: S = 2 · ∑ i(1/3)ⁱ + ∑ (1/3)ⁱ.
The plain geometric sum ∑ (1/3)ⁱ = 1/(1 − 1/3) = 3/2.
The arithmetic-geometric sum ∑ i · rⁱ = r/(1 − r)² for |r| < 1. With r = 1/3 this gives (1/3)/(2/3)² = 3/4.
So S = 2(3/4) + 3/2 = 3/2 + 3/2 = 3.
Given:
g(1) = 1, g(2) = 5, g(3) = 6
For n > 3: g(n) = 2g(n−1) + g(n−2) − 2g(n−3)
Compute by direct substitution:
g(4) = 2·g(3) + g(2) − 2·g(1) = 2(6) + 5 − 2(1) = 12 + 5 − 2 = 15
g(5) = 2·g(4) + g(3) − 2·g(2) = 2(15) + 6 − 2(5) = 30 + 6 − 10 = 26
g(6) = 2·g(5) + g(4) − 2·g(3) = 2(26) + 15 − 2(6) = 52 + 15 − 12 = 55
For the bonus challenge: embed the recurrence in a 3×3 matrix and use fast matrix exponentiation (O(log n) multiplications) to compute g(n) mod 10⁹+7 for very large n.
Formula | Notes |
|---|---|
∑ i from 1 to n = n(n+1)/2 | Standard arithmetic sum |
∑ i² from 1 to n = n(n+1)(2n+1)/6 | Sum of squares |
∑ rⁱ from i = 0 to ∞ = 1/(1−r) | Geometric series, |r| < 1 |
∑ i·rⁱ from i = 0 to ∞ = r/(1−r)² | Arithmetic-geometric, |r| < 1 |
Closed-form summations are exactly what you use when analysing the running time of nested loops. If an inner loop runs i times while i goes from 1 to n, the total work is ∑ i = n(n+1)/2, which is O(n²). Recurrence relations model recursive algorithms directly: mergesort's T(n) = 2T(n/2) + n is a recurrence you solve to get O(n log n).
Students forget to adjust the upper limit when the sum runs to 2ⁿ rather than n. Every standard formula you plug in must use the actual upper bound, not just "n."
When splitting ∑(2i + 1)rⁱ, students sometimes forget that the "1" term contributes its own geometric series. Both pieces must be evaluated.
With recurrence computations, a common slip is using g(n−1) when you meant g(n−2). Label your substitutions carefully.
The formula ∑ i·rⁱ = r/(1−r)² starts at i = 0. If your sum starts at i = 1, check whether the i = 0 term is zero (it is here, so no adjustment needed, but be aware).
⚠️ Summation problems frequently appear on exams. You are expected to know the closed forms for ∑ i and ∑ i² by heart.
⚠️ The subtraction method for arithmetic-geometric series is a standard exam technique. Practise it until the steps are automatic.
⚠️ Recurrence relation computation is straightforward marks, but the bonus matrix exponentiation idea connects to fast algorithms (a topic that returns in later courses).
True or False: ∑ i² from 1 to n = n(n+1)(n+2)/6.
Fill in the blank: The infinite geometric series ∑ rⁱ from i = 0 to ∞ converges when ______.
True or False: For the recurrence g(n) = 2g(n−1) + g(n−2) − 2g(n−3), you need exactly three base cases.
Fill in the blank: ∑ i·rⁱ from i = 0 to ∞ = ______ (in terms of r).
True or False: g(4) = 16 given g(1)=1, g(2)=5, g(3)=6 and the recurrence above.
Answers: 1. False (it is n(n+1)(2n+1)/6). 2. |r| < 1. 3. True. 4. r/(1−r)². 5. False (g(4) = 15).
Q: Evaluate ∑ (i² − i) from i = 1 to 2ⁿ and express in the form 2ᵃ(2ᵇ − 1)/c.
A: Split into ∑ i² − ∑ i, substitute closed forms with upper limit 2ⁿ, simplify. Result: 2ⁿ(2²ⁿ − 1)/3, so a = n, b = 2n, c = 3.
Q: Compute ∑ (2i + 1)(1/3)ⁱ from i = 0 to ∞.
A: Decompose into 2·∑ i(1/3)ⁱ + ∑(1/3)ⁱ. Using the formulas for geometric and arithmetic-geometric series, the answer is 3.
Q: Given g(1)=1, g(2)=5, g(3)=6 and g(n) = 2g(n−1) + g(n−2) − 2g(n−3), find g(5).
A: First compute g(4) = 15, then g(5) = 2(15) + 6 − 2(5) = 26.
Q: Why does the infinite series ∑ (2i+1)(1/3)ⁱ converge?
A: The geometric factor (1/3)ⁱ decays exponentially. Even though (2i+1) grows linearly, the exponential decay dominates, so the terms shrink to zero fast enough for convergence.
This material connects directly to algorithm analysis, where summations give you exact operation counts and recurrences model recursive runtime. The matrix exponentiation bonus ties into modular arithmetic and linear algebra, both of which recur throughout discrete maths and computer science theory.
summation, closed form, sigma notation, sum of squares, geometric series, arithmetic-geometric series, infinite series, convergence, recurrence relation, linear recurrence, base case, matrix exponentiation, COT 3100, discrete mathematics, UCF, algorithm analysis