Induction and Proof Strategies: Geometric Series, Divisibility, and Evenness

Course context and guidance

• Four course representatives for 1602 and 6002; contact details provided for feedback routing via associate director of education; you can contact any representative, not just your enrolled course, to pass feedback.
• Slides/pages location: information under the extension app section on the Waddle page.
• Instructor encouragement: asking questions during or after lecture helps gauge understanding.
• Practical notes about technical issues with proof tools (Daphne/VSCode): occasional timeouts; sometimes restarting the tool helps; differences across command line vs IDE implementations.
• The instructor emphasizes clarity: state what you aim to prove at the top of each slide and avoid using a proof step as an assumption of what you are trying to prove.
• Terminology notes: be careful with which variable is the induction variable (n vs k vs i) and what to replace; do not reuse the same symbol as both a bound and a variable to increment.
• Real-world relevance: the proofs illustrate standard induction techniques, problem decomposition, and translating informal divisibility statements into formal predicates (e.g., Divides).

Key concepts: induction and proof strategy

• Induction structure:
  • Base case: prove the statement for the initial value (e.g., n = 0 or n = 1, depending on the problem).
  • Inductive hypothesis (IH): assume the statement holds for some arbitrary value (often n = k).
  • Inductive step: prove that if the IH holds, then the statement holds for the next value (often n = k+1). In some problems you prove for n+1, in others you may need a step of +2 or another increment.
• Important caution: do not use the statement you are trying to prove as part of your assumption; the inductive step must derive the next case from the assumption, not assume the conclusion.
• Notation patterns:
  • In a geometric sum, r is a constant (the common ratio); the sum is
    Sn = \sum{i=0}^{n} r^{i}.
  • For r ≠ 1, the closed form is
    \sum_{i=0}^{n} r^{i} = \frac{r^{n+1}-1}{r-1}.
  • The base case often uses n = 0 (giving S_0 = 1) and then induction on n.
• Strategy tip: when proving by induction, you can explicitly rewrite the left-hand side to reveal a part that matches the IH, then manipulate algebraically to reach the target right-hand side.
• When problems are stated in words (e.g., divisibility), translate to a formal predicate (e.g., Divides) and use existence statements to capture divisibility (e.g., for some integer m, 3m = target).
• If you encounter a tool (Daphne) not immediately proving a step, you can reveal intermediate facts incrementally and sometimes reformulate the proof in a different style (e.g., from a calc view to a set of assertions).

Geometric series by induction: base case, IH, and step

• Problem statement (geometric sum): Prove for r > 1 and all n ≥ 0,
  \sum_{i=0}^{n} r^{i} = \frac{r^{n+1}-1}{r-1}.
• Base case: n = 0
  • Left-hand side: \sum_{i=0}^{0} r^{i} = r^{0} = 1.
  • Right-hand side: \frac{r^{0+1}-1}{r-1} = \frac{r-1}{r-1} = 1.
  • Base case holds for r ≠ 1; note the formula would fail if r = 1 due to division by zero.
• Inductive hypothesis (IH): Assume the formula holds for n = k, i.e.
  \sum_{i=0}^{k} r^{i} = \frac{r^{k+1}-1}{r-1}.
• Inductive step: show it holds for n = k+1.
  • Start with \sum{i=0}^{k+1} r^{i} = \left(\sum{i=0}^{k} r^{i}\right) + r^{k+1}.
  • Apply IH: = \frac{r^{k+1}-1}{r-1} + r^{k+1}.
  • Put over a common denominator:
    = \frac{r^{k+1}-1}{r-1} + \frac{r^{k+1}(r-1)}{r-1} = \frac{r^{k+1}-1 + r^{k+1}r - r^{k+1}}{r-1} = \frac{r^{k+2}-1}{r-1}.
• Conclusion: by base case and inductive step, the formula holds for all n ≥ 0 when r > 1 (and r ≠ 1 to avoid division by zero).
• Additional teaching notes from the lecture:
  • It can be helpful to state the objective at the top of each slide; this clarifies what you are aiming to prove and avoids confusion about the direction of the proof.
  • Visualizing the left-hand side (LHS) and right-hand side (RHS) as two ends of a chain that you connect through algebraic manipulation.
  • In the demonstration, an explicit reminder that you should not use the inductive step as an assumption of the conclusion; the step should derive the next case strictly from the IH.
• Practical tip: if a tool times out during the demonstration, restart or switch environment (e.g., from command line to an IDE) to resume the proof progression.

Divisibility by 3: the sequence 4^n - 1

• Problem statement: For all n ≥ 1, show that 4^n - 1 is divisible by 3.
• Base case: n = 1
  • 4^1 - 1 = 3, which is divisible by 3.
• Inductive hypothesis (IH): Assume for some k ≥ 1 that 4^k - 1 is divisible by 3, i.e., there exists an integer m such that
  4^{k} - 1 = 3m.
• Inductive step: prove for n = k + 1.
  • Compute:
    4^{k+1} - 1 = 4^{k} \cdot 4 - 1 = 4^{k} \cdot 3 + 4^{k} - 1.
  • Substitute the IH expression: = 3 \cdot 4^{k} + (4^{k} - 1) = 3 \cdot 4^{k} + 3m = 3(m + 4^{k}).
  • Since m and 4^{k} are integers, m + 4^{k} is an integer; thus 3 times an integer, i.e., 3 divides 4^{k+1} - 1, holds.
• Conclusion: by base case and inductive step, 4^n - 1 is divisible by 3 for all n ≥ 1.
• Formalization notes from the lecture:
  • When problems are stated in words, translate divisibility into a predicate: Divides(a,b) ≡ ∃t ∈ Z such that b = a t. Then show Divides(3, 4^n - 1).
  • In the demonstration, a constructive witness m is used: 4^{k} - 1 = 3m; then 4^{k+1} - 1 = 3(m + 4^{k}).
  • Daphne (proof assistant) can require explicit existence of the witness; if it cannot find such a witness, you may need to introduce it in a different form or provide additional justification.
• Practical note: exploring a recurrence or recursive power function (below) can help show how powers like 4^n behave under induction; Daphne may require a termination guarantee (decreases) when using recursion.

A note on proving with a recursive function and termination (Daphne/recursion discussion)

• Example shown: define a recursive function power(a, n) to compute a^n, e.g.,
  • power(a, 0) = 1
  • power(a, n) = a × power(a, n-1) for n > 0
• Termination issue: to guarantee termination in a recursive proof assistant, you may need a measure that decreases with each recursive call (a “decreases” clause).
  • In the lecture, the instructor notes adding a decreases clause can help Daphne determine termination, especially when avoiding a simple k-based recursion (which can trigger a termination check error).
• Practical takeaway: if a tool complains about termination, restructure recursion to ensure a obvious decreasing measure (e.g., n decreases by 1 each call) or revert to a non-recursive proof approach where possible.

An alternative induction pattern: proving every second natural number is even

• Property P(n): n is even.
• Base case: n = 0
  • 0 is even, so P(0) holds.
• Inductive step (a “step of 2”): show that if P(k) holds, then P(k+2) holds for all k ≥ 0.
  • Approach: write k in the form k = 2m (since P(k) holds then k is even, so k = 2m for some m ∈ N).
  • Then k + 2 = 2m + 2 = 2(m + 1), which is even, hence P(k+2) holds.
• Discussion about odd k:
  • If k is odd, then P(k) is false; the inductive hypothesis P(k) ⇒ P(k+2) becomes a vacuously true implication, so the induction step does not require handling odd k explicitly.
  • This approach proves P(n) for all even n by a 2-step induction: from 0 you reach 2, then 4, 6, etc.
• Conclusion: using a step of 2 demonstrates that every even natural number is even, and it illustrates how induction can be adapted when the natural progression is not by 1 but by larger steps (2, in this case).
• Reflective takeaway: when the statement is about a subsequence (e.g., even numbers), a step of size 2 (or a suitable n-offset) is often the natural induction step; be mindful of what the IH covers and how it interacts with the base case and step size.

Practical tips and reflections from the lecture

• Start with a clear goal: state what you are trying to prove at the top of each slide/section to avoid confusion about the direction of the proof.
• Use the IH effectively: explicitly replace the IH instance into the larger expression to reveal the structure that matches the desired RHS.
• Manage variable naming carefully: avoid reusing the same symbol for the bound and the increment; use k for the IH instance and n for the general statement, or vice versa, but keep it consistent.
• When translating problems into formal predicates (e.g., divisibility), write the formal statements explicitly (e.g., Divides(a,b) ≡ ∃t, b = a t) to guide the proof structure.
• If an intermediate step seems verbose, test whether it is essential by attempting to skip it; proof assistants may reveal which steps are strictly necessary.
• If you encounter a tool-timeout or an inconclusive proof, try alternate representations (calc, set-of-assertions) or switch tools, as demonstrated in the lecture.
• Real-world relevance: these examples illustrate common patterns in mathematical proofs with induction, including handling base cases, IH, algebraic manipulation, and translating informal arguments into formal steps.

Recap: structure and key ideas to remember

• Induction structure: base case, inductive hypothesis, inductive step; ensure the step derives the next case from the IH, not the other way around.
• For geometric sums, the closed form with r ≠ 1 is derived by showing the sum satisfies the recurrence and matches the base case.
• For divisibility, the proof often relies on expressing the target as a multiple of the divisor using an IH witness (e.g., 4^k - 1 = 3m) and factoring out the divisor.
• When proving properties about subsequences (e.g., even numbers), consider stepping by 2 and analyze the form of n (e.g., n = 2m) to maintain the property.

Summary of key equations and predicates used

• Geometric sum formula (r > 1):
  \sum_{i=0}^{n} r^{i} = \frac{r^{n+1}-1}{r-1}.
• Base case for geometric sum: n=0: \sum_{i=0}^{0} r^{i} = 1 = \frac{r^{1}-1}{r-1}.
• Inductive step algebra (sketch):
  \sum{i=0}^{k+1} r^{i} = \left(\sum{i=0}^{k} r^{i}\right) + r^{k+1} \ = \frac{r^{k+1}-1}{r-1} + r^{k+1} \ = \frac{r^{k+2}-1}{r-1}.
• Divisibility predicate (Divides):
  Divides(a,b) \equiv \exists t \in \mathbb{Z},\quad b = a t.
• Divisibility example: Divides(3, 4^{n}-1) with 4^n - 1 = 3m ⇒ 4^{n+1}-1 = 3(m+4^n).
• Inductive step for n≥1: if 4^k - 1 = 3m, then
  4^{k+1}-1 = 3m + 3\cdot 4^k = 3(m + 4^k).
• Even numbers via step 2: if k = 2m, then k+2 = 2(m+1) is even.

Note on formatting in this note set

• All mathematical expressions are presented in LaTeX within double-dollar delimiters as required.
• The notes are organized as bullet points under clear headings to mimic a comprehensive study guide that can replace the original source.