Session 5A
Induction structure
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- Mathematical induction proves statements indexed by integers (usually n >= some start). The logic is like dominoes: you prove a base case (the first domino falls), and then you prove that if the statement is true for an arbitrary k, it must also be true for k+1 (each domino knocks down the next). Formally, induction proves a universal statement over the integers. It is not "assume what you want and done." The inductive step must show how truth at k forces truth at k+1.
- Induction proofs have a standard form: (1) Base case: verify n = n0. (2) Inductive hypothesis: assume the statement holds for n = k. (3) Inductive step: using the hypothesis, prove it holds for n = k+1. The main beginner pitfall is not using the hypothesis in a logically valid way or accidentally proving the same n twice. The right mindset is: the hypothesis is a tool you may use exactly for k, and your job is to transform the k+1 statement until it contains the k statement inside it.
Worked examples
- Sum 1 + 2 + ... + n = n(n + 1)/2 for n >= 1.
Practice
- 1Prove: 1 + 3 + 5 + ... + (2n - 1) = n^2.
- 2Prove: 2^n >= n + 1 for n >= 0.
MCQ
In the inductive step, you must show: