Lecture Notes: Mathematical Induction and Recursion

Course logistics and announcements

• Class representatives have been chosen: four reps for COMM 1600 and two reps for 06/1960, including both postgraduate and undergraduate students. The reps will help relay information and organize meetings; you can contact them or talk to the conveners directly.
• Video slots: the last video will come a bit late this week because tutors are adapting to the new idea of including videos in the course. There may be delays; two videos per week are the target, but illness or other delays can occur.
• Quizzes and extensions: the quiz from last week is closed. Extensions must be requested via the course app for proper documentation; email extension requests may be ignored.
• Course progress: you’ve completed several mini-assignments; you’re gaining the hang of them.
• Reminder about next content: this session introduces mathematical induction; a fast recap of recursion will also be included for those unfamiliar with it. If you’re not comfortable with recursion, watch Aneesh’s video and study separately.
• Structural induction (lists and trees) will be covered in the following weeks; future lectures (e.g., Dirk’s) will discuss those structures.
• The instructor emphasized accessibility of information and reminded you to use Ed for updates and contact details.

What is mathematical induction? Key ideas and setup

• Purpose: to prove that a property holds for every integer in a set (e.g., all natural numbers greater than or equal to some value).
• Why not check every value? There are infinitely many integers, so we need a general method.
• Induction structure (often called natural induction):
  • Base case: prove the property holds for the starting value s (often s = 0 for natural numbers).
  • Induction step: prove that for any k ≥ s, if the property P(k) holds, then P(k+1) holds (the usual pattern is +1; sometimes the step pattern varies in tutorials).
  • Conclusion: the property holds for all integers k ≥ s.
• Important note: in this course, after establishing induction for numbers, there will also be a discussion of structural induction for other structures (lists, trees) in future weeks.

Natural numbers and base/induction steps

• When restricting to natural numbers (including zero, no negatives):
  • Base case: prove P(s) with s = 0, i.e., prove P(0) holds.
  • Induction step: prove that for all k ≥ 0, P(k) ⇒ P(k+1).
• General pattern in the slides: prove base case P(0) (or P(s)); then prove that if P(k) holds, P(k+1) holds. From these two pieces, P(n) holds for all n ≥ 0.
• The two-part structure is essential: base case + induction step.

A classic induction example: the sum of the first n natural numbers

• Goal: prove that for all n ≥ 0,
  1 + 2 +
  \dots + n = rac{n(n+1)}{2}.
• Notation note: this can be written with sigma notation as
  oxed{ \sum_{i=0}^{n} i = rac{n(n+1)}{2} }.
• Base case: n = 0
  • Left-hand side (LHS): $ext{LHS} = 0,$ since the sum from 0 to 0 is just 0.
  • Right-hand side (RHS): ext{RHS} = rac{0(0+1)}{2} = 0.
  • So the base case holds (0 = 0).
• Inductive hypothesis (IH): assume for some k ≥ 0 that
  $1 + 2 + \dots + k = \frac{k(k+1)}{2}.$
• Inductive step: show that the property holds for k+1:
  • Consider the sum up to k+1:
    $1 + 2 + \dots + k + (k+1).$
  • Using IH, replace the part up to k:
    $\left( \frac{k(k+1)}{2} \right) + (k+1).$
  • Combine terms:
    $\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$
  • This is exactly the formula for n = k+1, i.e.,
    $1 + 2 + \dots + (k+1) = \frac{(k+1)(k+2)}{2}.$
• Conclusion: since the base case holds and the IH implies the next case, the statement holds for all n ≥ 0.
• Key takeaway: base case ensures a starting point; the inductive step propagates the truth from k to k+1 for all k ≥ 0.
• Common pitfall: skipping the base case leads to invalid conclusions (e.g., trying to prove I = I+1 with no start point).

A second induction example: a geometric series

• For all n ≥ 0 and a fixed ratio r > 1, prove
  oxed{\sum_{i=0}^{n} r^{i} = \frac{r^{n+1} - 1}{r-1}}.
• Base case: n = 0
  • LHS: $r^{0} = 1.$
  • RHS: $\frac{r^{0+1} - 1}{r-1} = \frac{r - 1}{r - 1} = 1.$
  • Valid for r ≠ 1; the condition r > 1 ensures the denominator is nonzero.
• Inductive hypothesis: assume for some k ≥ 0 that
  $\sum_{i=0}^{k} r^{i} = \frac{r^{k+1} - 1}{r-1}.$
• Inductive step: show for k+1
  • LHS up to k+1:
    $\sum<em>{i=0}^{k+1} r^{i} = \left( \sum</em>{i=0}^{k} r^{i} \right) + r^{k+1}.$
  • Use IH to replace the sum up to k:
    $= \frac{r^{k+1} - 1}{r-1} + r^{k+1}.$
  • Put over common denominator and simplify:
    $= \frac{r^{k+1} - 1 + r^{k+1}(r-1)}{r-1} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r-1} = \frac{r^{k+2} - 1}{r-1}.$
  • This matches the formula with n = k+1.
• Conclusion: the geometric-series formula holds for all n ≥ 0 when r > 1.
• Example check with r = 3, n = 2:
  • LHS: $3^{0} + 3^{1} + 3^{2} = 1 + 3 + 9 = 13.$
  • RHS: $\frac{3^{3} - 1}{3 - 1} = \frac{27 - 1}{2} = \frac{26}{2} = 13.$

Recursion recap: connecting induction to recursive definitions

• Recursion idea: define a function in terms of itself on smaller inputs with a base case to stop.
• Example: factorial
  • Definition: $0! = 1,$ and for n ≥ 1, $n! = n \cdot (n-1)!.$
  • Termination base: when n = 0, return 1.
  • Worked example: compute $4! = 4 \cdot 3! = 4 \cdot (3 \cdot 2!) = 4 \cdot 3 \cdot (2 \cdot 1!) = 4 \cdot 3 \cdot 2 \cdot (1 \cdot 0!) = 4 \cdot 3 \cdot 2 \cdot 1 = 24.$
• Why induction relates to recursion:
  • Induction is a natural tool for proving properties of recursively defined quantities, because the recursive definition inherently relies on a base case and a step that builds from smaller instances.
• Quick Daphne/Dafny recap (context from the lecture):
  • Dafny can sometimes prove induction automatically or show steps; you can turn induction off ("induction false") to see how a manual proof would proceed.
  • When proving by hand, you may use a calc block to chain equalities and show the IH is used to reduce the left-hand side to the right-hand side.
  • Pre-conditions matter: if the precondition is never satisfied, the proof may be vacuously true or not applicable; always check the starting point where the induction can actually be applied.
• Manual induction exercise (to illustrate the process):
  • Instead of the standard k to k+1, you can structure the IH to relate n−1 to n (i.e., assume P(n−1) and prove P(n)) or use a calc-based approach to connect the induction hypothesis to the target expression.
  • This helps illustrate how an inductive proof can be written in different but equivalent forms.

Important insights and practical tips from the lecture

• Base case is crucial: never skip the base case; without it, the inductive chain has no starting point.
• The inductive step is the mechanism by which truths propagate: if P(k) holds, then P(k+1) must hold for all k in the domain.
• The sigma notation is a compact way to express summations and is essential for translating sums into closed forms.
• When working with proofs, look for places to substitute the IH into the target expression and simplify to the desired form.
• Recursion and induction are closely linked; understanding one helps with the other.
• If a tool (like Dafny) solves a problem automatically, try turning off the feature to practice manual proof techniques and to understand the underlying steps.
• When extending induction to new domains (like structures in structural induction), the same base-step pattern applies, but the notion of what constitutes a base case and how the “next” structure is formed changes (e.g., elements of a list or nodes of a tree).

Looking ahead: what’s coming in future lectures

• Structural induction: the same two-part idea applied to data structures such as lists and trees.
• Expect more examples and practice problems that connect induction to real-world algorithms and proofs.
• The course will continue to integrate recursion, induction, and formal proofs to build a solid foundation for reasoning about algorithms and data structures.