Mathematical Induction: Proving Summation Formulas

Initial Problem: Volume and Surface Area Equation

• Given Information:

  • The link (length) of an object is twice its width ($L = 2W$).

  • The total surface area of the exterior walls is $5000 ext{ ft}^2$ for a rectangular shape.

• Formulating Surface Area Equation:

  • The four walls consist of two front/back walls and two side walls.

  • Front/back walls: Each has area $L imes H$. Since there are two, this is $2LH$.

  • Side walls: Each has area $W imes H$. Since there are two, this is $2WH$.

  • Total surface area: $2WH + 2LH = 5000$.

• Substitution and Simplification:

  • Substitute $L = 2W$ into the surface area equation: $2WH + 2(2W)H = 5000$.

  • This simplifies to $2WH + 4WH = 5000$.

  • Combined: $6WH = 5000$.

• Solving for Height (H):

  • Divide by $6W$: $H = rac{5000}{6W}$.

• Volume Equation in terms of Width (W):

  • The volume of a rectangular prism is $V = LWH$.

  • Substitute $L = 2W$: $V(W) = (2W)WH = 2W^2H$.

  • Substitute the expression for $H$: $V(W) = 2W^2 imes rac{5000}{6W}$.

  • Simplify the volume equation: $V(W) = rac{10000W^2}{6W} = rac{5000W}{3}$.

Review of Summation Formulas

• Sum of first n integers: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

• Sum of first n squares: $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

• Sum of first n cubes: $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$

Mathematical Induction: Core Analogy and Process

• Analogy: Knocking down a line of dominos.

  • Base Case: The first domino (n=1) falls.

  • Induction Hypothesis/Step: If any domino k falls, then the next domino (k+1) will also fall.

• Purpose: Proving these summation formulas are true for all natural numbers n.

Proof by Induction: Sum of First n Integers

• Statement to Prove: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

• 1. Base Case (Show true for $n=1$):

  • Left Hand Side (LHS): $\sum_{i=1}^{1} i = 1$

  • Right Hand Side (RHS): $\frac{1(1+1)}{2} = \frac{1 \times 2}{2} = 1$

  • Conclusion: Since LHS = RHS, the statement is true for $n=1$. (The first domino falls.)

• 2. Induction Hypothesis (Assume true for some k < n):

  • Assume the statement is true for some integer $k$. Specifically, assume: $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$.

• 3. Induction Step (Show true for $k+1$):

  • Goal: We want to show that the statement is true for $k+1$, meaning: $\sum_{i=1}^{k+1} i = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}$.

  • Start with LHS: $\sum_{i=1}^{k+1} i$

  • Expand the sum: $1 + 2 + 3 + \dots + k + (k+1)$.

  • Rewrite using summation notation: $\left(\sum_{i=1}^{k} i\right) + (k+1)$.

  • Apply Induction Hypothesis: Substitute the assumed formula for the sum up to k:
    $\frac{k(k+1)}{2} + (k+1)$.

  • Find a common denominator:
    $\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2}$.

  • Factor out the common term $(k+1)$:
    $\frac{(k+1)(k+2)}{2}$.

  • Result: This matches the RHS that we aimed for, so the statement holds for $k+1$.

• 4. Conclusion (By mathematical induction):

  • By mathematical induction, the sum of $i$ from $1$ to $n$ is equal to $\frac{n(n+1)}{2}$ for all natural numbers $n$.

Proof by Induction: Sum of First n Squares

• Statement to Prove: $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

• 1. Base Case (Show true for $n=1$):

  • LHS: $\sum_{i=1}^{1} i^2 = 1^2 = 1$

  • RHS: $\frac{1(1+1)(2(1)+1)}{6} = \frac{1 \times 2 \times 3}{6} = 1$

  • Conclusion: Since LHS = RHS, the statement is true for $n=1$. The base case holds.

• 2. Induction Hypothesis (Assume true for some k < n):

  • Assume the statement is true for some integer $k$. Specifically, assume: $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$.

• 3. Induction Step (Show true for $k+1$):

  • Goal: We want to show that the statement is true for $k+1$, meaning: $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$.

  • Start with LHS: $\sum_{i=1}^{k+1} i^2$

  • Rewrite using summation notation: $\left(\sum_{i=1}^{k} i^2\right) + (k+1)^2$.

  • Apply Induction Hypothesis: Substitute the assumed formula for the sum up to k:
    $\frac{k(k+1)(2k+1)}{6} + (k+1)^2$.

  • Find a common denominator: Force a common denominator of 6:
    $\frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6} = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6}$.

  • Factor out the common term $(k+1)$:
    $\frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$.

  • Simplify the expression inside the bracket: Distribute and combine like terms:
    $\frac{(k+1)[2k^2 + k + 6k + 6]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6}$.

  • Factor the quadratic term $(2k^2 + 7k + 6)$: This factors into $(2k+3)(k+2)$.
    (Self-check: $(2k+3)(k+2) = 2k^2 + 4k + 3k + 6 = 2k^2 + 7k + 6$)

  • Substitute the factored quadratic back:
    $\frac{(k+1)(k+2)(2k+3)}{6}$.

  • Result: This matches the RHS that we aimed for, so the statement holds for $k+1$.

• 4. Conclusion (By mathematical induction):

  • By mathematical induction, the sum of $i^2$ from $1$ to $n$ is equal to $\frac{n(n+1)(2n+1)}{6}$ for all natural numbers $n$.

Grading an Induction Proof

• An induction proof is considered a "mathematical essay" requiring precise language and organized steps.

• Typical Point Breakdown (e.g., for a 15-point problem):

  • Base Case: $3$ points (Statement, calculation of LHS/RHS, conclusion).

  • Induction Hypothesis: $2$ points (Clearly stating the assumption for $k$).

  • Induction Step Statement: $1$ point (Clearly stating the goal to prove for $k+1$).

  • Algebraic Work in Induction Step: $7$ points (Demonstrating the transformation from the k-sum to the k+1 sum).

  • Conclusion: $2$ points (Formal statement by mathematical induction).

• Key Emphasis: The language in each section (e.g., "Since LHS = RHS, the statement is true for $n=1$") is crucial for a complete and correct proof.

• Algebraic steps must be shown, and simplification shortcuts are accepted if algebraically correct.

Connection to Previous Lectures

• These summation formulas are directly applicable to problems encountered earlier, particularly when calculating the area under a curve using Riemann sums with $n$ rectangles. Previously, we derived expressions like the sum of $i^2$ from $1$ to $n$ when setting up these problems.

• Now, instead of leaving the sum in that form, we can substitute the derived closed-form formulas (e.g., $\frac{n(n+1)(2n+1)}{6}$ for $\sum i^2$) to simplify calculations and find a direct formula in terms of $n$.