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 loop in 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<em>{i=s}^{t} a</em>i = N$ and $\sum<em>{i=s}^{t} b</em>i = 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<em>{i=s}^{t} c \cdot a</em>i = c \cdot \sum<em>{i=s}^{t} a</em>i = c N$

  • Concept: 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<em>{i=s}^{t} (a</em>i \pm b<em>i) = \sum</em>{i=s}^{t} a<em>i \pm \sum</em>{i=s}^{t} b_i = N \pm M$

  • Concept: 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 t$

  • Concept: 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^2$

  • $A \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<em>{i=1}^{n} i^3 = 1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 = (\sum</em>{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