Computer Science Matrix - Summation and Induction
Introduction to Summation Notation
Sigma Notation (\sum): This is a compact way to represent a sum of a sequence of numbers, analogous to a
for loopin computer science.Components:
\sum: The sigma symbol, indicating summation.
i: The index variable (or generator variable), which changes with each term.
s: The starting index (lower limit).
t: The terminal index (upper limit).
a_i: The generator or general term, which defines the pattern of the terms being summed.
Evaluating Sums
To evaluate a sum, substitute the index variable with values from the starting index up to the terminal index, and then add the resulting terms.
Example 1: Evaluate \sum_{i=0}^{5} 3i^2
Start index: i=0
Terminal index: i=5
Generator: 3i^2
Expansion: (3 \cdot 0^2) + (3 \cdot 1^2) + (3 \cdot 2^2) + (3 \cdot 3^2) + (3 \cdot 4^2) + (3 \cdot 5^2)
Calculation: 0 + 3 + 12 + 27 + 48 + 75 = 165
Example 2: Evaluate \sum_{i=1}^{3} (4i^2 + 5)
Start index: i=1
Terminal index: i=3
Generator: (4i^2 + 5)
Expansion: (4 \cdot 1^2 + 5) + (4 \cdot 2^2 + 5) + (4 \cdot 3^2 + 5)
Calculation: (4 + 5) + (16 + 5) + (36 + 5) = 9 + 21 + 41 = 71
Example 3: Evaluate \sum_{i=1}^{4} \frac{1}{i^2}
Start index: i=1
Terminal index: i=4
Generator: \frac{1}{i^2}
Expansion: \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2}
Calculation: \frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \frac{1}{16} (Note: The calculation was not completed in the transcript, but the expansion is key).
Writing Sums in Sigma Notation
The goal is to reverse the process of evaluation: given an expanded sum, find its compact sigma notation.
Rule of Thumb: If something stays the same throughout all terms, it stays the same in the generator.
Example A: Write the sum 2 + 4 + 6 + 8 + 10 in sigma notation.
Pattern Recognition: All numbers are even, multiples of 2.
Generator: 2i (or 2k, etc.).
Indices:
For i=1, 2(1)=2
For i=2, 2(2)=4
…
For i=5, 2(5)=10
Sigma Notation: \sum_{i=1}^{5} 2i
Example B: Write the sum 2 + 4 + 8 + 16 + 32 in sigma notation.
Pattern Recognition: All numbers are powers of 2.
Generator: 2^i
Indices:
For i=1, 2^1=2
For i=2, 2^2=4
…
For i=5, 2^5=32
Sigma Notation: \sum_{i=1}^{5} 2^i
There can be multiple ways to represent a sum with different starting indices, but the overall sequence of terms remains the same.
Example C: Write the sum f(\frac{1}{n}) + f(\frac{2}{n}) + f(\frac{3}{n}) + \dots + f(\frac{n}{n}) in sigma notation.
Pattern Recognition: The function f and the denominator n remain constant. The numerator increases by 1 each time.
Generator: f(\frac{i}{n})
Indices:
For i=1, f(\frac{1}{n})
For i=2, f(\frac{2}{n})
…
For i=n, f(\frac{n}{n})
Sigma Notation: \sum_{i=1}^{n} f(\frac{i}{n})
Rules for Sums (Properties of Summation)
These rules are derived from properties of addition and multiplication.
Let \sum{i=s}^{t} ai = N and \sum{i=s}^{t} bi = M, and c is a constant.
Rule 1: Constant Multiple Rule
If a constant c is multiplied by the generator, it can be factored out of the summation:
\sum{i=s}^{t} c \cdot ai = c \cdot \sum{i=s}^{t} ai = c NConcept: Just as you can factor out a common term from an expanded sum, you can factor out a constant from a sigma notation.
Rule 2: Sum/Difference Rule
The sum (or difference) of two generators can be split into the sum (or difference) of two separate summations:
\sum{i=s}^{t} (ai \pm bi) = \sum{i=s}^{t} ai \pm \sum{i=s}^{t} b_i = N \pm MConcept: This allows distributing the summation across terms being added or subtracted within the generator.
Rule 3: Sum of a Constant
If the generator is just a constant c (i.e., it doesn't depend on the index i):
\sum_{i=s}^{t} c = c \cdot (t - s + 1)Special Case: If the starting index is i=1 (s=1):
\sum_{i=1}^{t} c = c \cdot tConcept: This is equivalent to repeated addition, which is multiplication (e.g., 5+5+5 = 5 \times 3).
This rule holds even if the constant is negative or if subtraction is involved.
Application: Approximating Area with Rectangles (Riemann Sums)
Problem: Approximate the area under the curve f(x) = x^2 on the interval [0, 1] using n right-endpoint rectangles.
Step 1: Calculate the width of each rectangle (\Delta x or base)
\Delta x = \frac{b-a}{n} = \frac{1-0}{n} = \frac{1}{n}
Step 2: Determine the heights of the rectangles
Using right endpoints, the x-values for the heights are rac{1}{n}, rac{2}{n}, rac{3}{n}, \dots, rac{n}{n}.
Heights: f(\frac{1}{n}), f(\frac{2}{n}), f(\frac{3}{n}), \dots, f(\frac{n}{n})
Step 3: Write the approximate area (A) as an expanded sum
A \approx \Delta x \cdot [f(\frac{1}{n}) + f(\frac{2}{n}) + f(\frac{3}{n}) + \dots + f(\frac{n}{n})]
A \approx \frac{1}{n} [f(\frac{1}{n}) + f(\frac{2}{n}) + f(\frac{3}{n}) + \dots + f(\frac{n}{n})]
Step 4: Convert the expanded sum to sigma notation
A \approx \frac{1}{n} \sum_{i=1}^{n} f(\frac{i}{n})
Step 5: Substitute the function f(x) = x^2 into the sum
A \approx \frac{1}{n} \sum_{i=1}^{n} (\frac{i}{n})^2
Step 6: Simplify the expression using summation rules
A \approx \frac{1}{n} \sum_{i=1}^{n} \frac{i^2}{n^2}
Since n is a constant with respect to the index i, n^2 can be factored out:
A \approx \frac{1}{n} \cdot \frac{1}{n^2} \sum_{i=1}^{n} i^2A \approx \frac{1}{n^3} \sum_{i=1}^{n} i^2
This result shows that to find the exact area, a formula for the sum of squares (\sum i^2) is needed.
Special Summation Formulas
These formulas provide immediate values for common sums, eliminating the need for manual expansion and calculation.
1. Sum of the First n Integers (Gauss's Formula)
Formula: \sum_{i=1}^{n} i = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}
Origin: Attributed to Carl Friedrich Gauss. He observed that pairing the first and last numbers (1 and n), second and second-to-last (2 and n-1), etc., always yields the sum (n+1). There are rac{n}{2} such pairs.
Example: For n=100, the sum is rac{100(100+1)}{2} = 50 \cdot 101 = 5050.
2. Sum of the First n Squares
Formula: \sum_{i=1}^{n} i^2 = 1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
This formula is more complex and relates to geometric principles involving hexagons in 2D space.
3. Sum of the First n Cubes
Formula: \sum{i=1}^{n} i^3 = 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 = (\sum{i=1}^{n} i)^2
This formula relates to 3D principles, such as tetrahedrons.
These formulas are essential for simplifying expressions derived from applications like Riemann sums and should be memorized.
Mathematical Induction
Purpose: To rigorously prove that a mathematical statement (or formula) is true for all natural numbers.
Motivation: While we can test a formula with a few numbers, we cannot test it for infinitely many. Induction provides a formal proof method.
Analogy: The