Lecture Notes: Induction, Sigma Notation, Lemmas, and Alternating Sum Identity

Announcements and course policy

  • AI policy reminder: AI is not permitted in this course; using AI-generated work is treated as academic misconduct and will be investigated. Recordings may be reviewed.
  • The teacher referenced Daphne (a tooling/writing environment) and how it handles proofs and lemmas; not all proofs are automatically proven by Daphne and some require using already-proven lemmas.
  • There was a quick recap of a previous example about divisibility by three: for all integers n ≥ 1, the statement 4^n − 1 is divisible by 3.
  • A note about postconditions in proofs: a postcondition can be used to express a universal claim (for all n) and then reason about n within a proof, sometimes by calling previously proven lemmas.
  • The tutorial is said to mirror this approach: use a for-all case and prove it via another lemma.

Sigma notation and recursive definitions

  • Sigma notation is introduced as a sum over an index: oldsymbol{ extstyle
    abla} \,\sum{i=m}^{n} ai (written as \sum{i=m}^{n} ai).
  • Start index m can be any integer; the end index is n.
  • Recursion/definition of sigma starting at m:
    • Base intuition: you start with the term am, then a{m+1}, up to a_n.
    • Recursive definition (useful for proofs):
      \sum{i=m}^{n} ai = \left(\sum{i=m}^{n-1} ai\right) + a_n \quad \text{for } m \le n.
  • If the lower limit exceeds the upper limit, the sigma is defined as zero:
    • Base case: if m > n, then \sum{i=m}^{n} ai = 0.
  • Starting index flexibility: the definition allows starting at any m (often m = 0 in many examples).
  • This sigma definition is used as the backbone for the distributive proof and for induction proofs involving sums.

Distributive property and induction framework

  • A key property shown: for any sequences (ai) and (bi),
    \sum{i=m}^{n} (ai + bi) = \left(\sum{i=m}^{n} ai\right) + \left(\sum{i=m}^{n} b_i\right).
  • Proving the property often uses induction on the upper index n (or on the length of the interval).
  • Induction setup (generic):
    • Base case: prove the statement for the minimal n (often when m > n, i.e., empty sum, or for n = m in single-term cases).
    • Inductive hypothesis: assume the statement holds for some arbitrary k (i.e., for the sum up to k).
    • Inductive step: prove the statement for k+1 using the hypothesis.
  • The speaker emphasized avoiding over-reliance on what Daphne can automatically prove; use induction hypotheses strategically to structure proofs.

Proving with lemmas and calling prior results

  • Sometimes a proof requires a supporting lemma that you prove separately (you can call this lemma from within your current proof).
  • Daphne allows calling previously proven lemmas within a file to reuse results.
  • The approach often involves:
    • Proving a basic lemma (e.g., a property of sigma or a sum identity).
    • Using that lemma to prove a more complex identity (e.g., splitting a sum into two sigmas).
  • The postcondition perspective: you separate the universal claim (for all n) from the concrete index manipulations, to keep the reasoning about n tractable inside the proof.

Recursion for sigma and examples

  • A recursive definition of a sigma that sums a generic term sequence:
    • Start with some m and go to n, summing a_i (which could be i, i^2, or a more complex term).
    • Base case is when m > n, giving 0; inductive step uses the decomposition up to n-1 plus the nth term.
  • This recursive perspective is used to prove distributive properties and to derive closed forms via induction.
  • An example pattern discussed: proving a general property of the sigma when the summand is itself a sum of two parts (ai + bi).
    • The idea is that the sum over i of ai + bi can be split into sum of ai plus sum of bi, by recursively applying the sigma definition.

Two concrete example walkthroughs

  • Example 1: splitting a sigma into two sub-sigmas

    • Goal: show that for any i, if you have a term that is a sum of two parts, you can separate the sigma into two sigmas:
      \sum{i=m}^{n} (ai + bi) = \sum{i=m}^{n} ai + \sum{i=m}^{n} b_i.
    • Approach: use the recursive definition of sigma and the induction hypothesis to argue that splitting at the top (n) and then applying the hypothesis yields the desired equality.
    • The speaker highlighted the idea of using the induction hypothesis to handle the inner sums and then reassembling the whole sigma.
    • This example was used to illustrate calling a lemma from within another lemma and to show how induction hypotheses are applied in a structured way.

  • Example 2: a recursive definition of sigma up to n, starting at m

    • Focus: define sigma from m to n recursively and discuss how to interpret terms like a_i when i = m, m+1, …, n.
    • Term patterns: a_i could be a simple term like I, or a function of i such as i^2, etc.
    • The interpretation: sigma from m to n of ai is the sum of terms starting with am, then a{m+1}, …, up to an.
    • Base case discussion: if m > n, the sum is zero; the inductive step proceeds by adding a_n to the sum up to n-1.

A more involved example: alternating sum of squares

  • The problem structure: compare two expressions for a sum with alternating signs:
    • Left-hand side (LHS):
      L(n) = \sum_{i=1}^{n} (-1)^{i-1} i^2.
    • Right-hand side (RHS) candidate: expressible as
      R(n) = (-1)^{n-1} \sum_{i=1}^{n} i = (-1)^{n-1} \cdot \frac{n(n+1)}{2}.
  • The identity to prove (by induction):
    \sum{i=1}^{n} (-1)^{i-1} i^2 \,=\, (-1)^{n-1} \sum{i=1}^{n} i \,=\, (-1)^{n-1} \cdot \frac{n(n+1)}{2}.
  • Why this structure works:
    • The signs alternate, so one needs a minus-one factor outside or inside the sigma to represent the alternation correctly.
    • Inside the sigma, the terms are i^2; outside, the factor (-1)^{n-1} captures the net sign pattern across the full sum.
  • Inductive proof outline (as discussed):
    • Base case n = 1:
    • LHS: L(1) = 1^2 = 1.
    • RHS: R(1) = (-1)^{0} \cdot 1 = 1.
    • Base case holds.
    • Inductive hypothesis: assume for some k that
      \sum_{i=1}^{k} (-1)^{i-1} i^2 = (-1)^{k-1} \frac{k(k+1)}{2}.
    • Inductive step: prove for k+1. Write
      L(k+1) = L(k) + (-1)^k (k+1)^2,
      R(k+1) = (-1)^k \sum{i=1}^{k+1} i = (-1)^k \left( \sum{i=1}^{k} i + (k+1) \right) = R(k) + (-1)^k (k+1).
    • Using the IH, replace L(k) with R(k) and reduce the problem to showing
      (-1)^k (k+1)^2 = (-1)^k (k+1) + \text{(something that equates via a known lemma)}.
    • The known lemma used is the standard sum formula
      \sum_{i=1}^{k} i = \frac{k(k+1)}{2}. (This was proven in an earlier lecture and is invoked here as a stepping stone.)
    • Equating the two sides reduces to the algebraic identity
      2 \cdot \frac{k(k+1)}{2} = k(k+1),
      which is true, confirming the inductive step.
  • Summary of the key takeaway for this example:
    • Some proofs require an auxiliary lemma (like Sk = \sum{i=1}^{k} i) proven earlier.
    • It may be helpful to manipulate both sides (left and right) and meet in the middle, using algebraic regrouping and factoring of signs to show equivalence.
    • The process demonstrates the utility of using both induction and auxiliary results to handle complex sums with alternating signs.

Structural notes and takeaways

  • The lecturer emphasized:
    • Build proofs with a clear base case and inductive step; identify the right place to apply the induction hypothesis.
    • When a proof becomes too intricate, consider using an auxiliary lemma (like a known sum formula) and/or presenting parts of the argument in stages (left-hand side vs right-hand side) and then showing they align.
    • It is acceptable to tackle parts of a proof off the main Daphne environment (on slides) if the platform makes certain steps unwieldy.
    • The approach to proofs often involves calling previously proven lemmas, using the distributive property of sigma, and careful algebraic manipulation of signs.
  • The lecturer indicated that a full treatment of structural induction would be left for a later session, but the current focus was on ordinary induction and the sigma-related lemmas.
  • Real-world relevance and connections:
    • These techniques underpin formal verification and reasoning about algorithms, where summations, recursion, and induction are common.
    • Understanding how to decompose sums and apply induction is foundational for proving correctness of programs and mathematical statements.

Quick recap of key formulas and identities

  • Sigma notation basics:
    • \sum{i=m}^{n} ai with base case m > n\Rightarrow \sum{i=m}^{n} ai = 0.
    • Recursion: \sum{i=m}^{n} ai = \left(\sum{i=m}^{n-1} ai\right) + a_n \quad (m \le n).
  • Distributive property of sigma:
    • \sum{i=m}^{n} (ai + bi) = \left(\sum{i=m}^{n} ai\right) + \left(\sum{i=m}^{n} b_i\right).
  • Common sum identity used in proofs:
    • Arithmetic series: \sum_{i=1}^{k} i = \frac{k(k+1)}{2}.
  • Alternating sum identity explored in detail:
    • Left-hand side (example):
      L(n) = \sum_{i=1}^{n} (-1)^{i-1} i^2.
    • Right-hand side candidate derived in the talk:
      R(n) = (-1)^{n-1} \sum_{i=1}^{n} i = (-1)^{n-1} \cdot \frac{n(n+1)}{2}.
    • The claimed equality: \sum_{i=1}^{n} (-1)^{i-1} i^2 = (-1)^{n-1} \frac{n(n+1)}{2}.
  • Divisibility example:
    • For all integers n ≥ 1,
      3 \mid (4^{n} - 1).