--- title: "Proof by Induction and Strong Induction" description: "Prove a statement for every natural number by settling a base case and showing each case forces the next. Strong induction assumes all earlier cases when one predecessor is not enough." canonical: https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC source: https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Proof by Induction and Strong Induction Prove a statement for every natural number by settling a base case and showing each case forces the next. Strong induction assumes all earlier cases when one predecessor is not enough. Subject: Mathematics · Area: Mathematical Thinking · Ages 18 to 19 Page: https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC ## Ready when they can - Prove a summation formula by induction with the inductive step written out - Use strong induction where the previous case alone is insufficient - Diagnose a flawed induction that skips the base case ## Lesson: Climbing proofs by induction *(drawing: Base case n equal to 1: left side is 1, and 1 times 2 over 2 is 1.)* *(drawing: Assume the k formula, add k plus 1, and simplify to the k plus 1 formula.)* Strong induction assumes every case from the start up to k, not only case k. It is needed when the next case depends on much earlier cases. Every integer above 1 has a prime factor: a composite n splits into factors strictly between 1 and n, far below n minus 1. Mei assumes every integer from 2 up to k has a prime factor, then proves it for k plus 1, which is strong induction. A proof with a correct step but no checked starting value proves nothing. The step only says the claim passes from k to k plus 1, assuming it holds at k. With no anchor the chain of links hangs on nothing. Dan is wrong to say the step alone is enough: always check the base case first, then write the step so the hypothesis is visibly used. Write the hypothesis before using it. For the sum proof it says the sum up to k equals k times k plus 1 over 2. Keep that line ready: the next algebra spends it to reach k plus 1. Test strong induction at n equal to 12. Split 12 as 3 times 4, both strictly between 1 and 12. The hypothesis range 2 to 11 covers both, so each brings its own prime factor. **Recap.** Anchor the chain with a base case, climb one link with the inductive step, and assume the whole range when one predecessor is not enough. ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Sets and Functions in the Language of Proof](https://lightmysky.com/learn/mathematics/sets-and-functions-in-the-language-of-proof-mt_XAcHX_3DVz) ## Optional connections - [Arithmetic Series and Sigma Notation](https://lightmysky.com/learn/mathematics/arithmetic-series-and-sigma-notation-mt_bAIPng87JO) ## Opens up - [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns) - [Recurrence Relations and Characteristic Roots](https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB) - [Divisibility and the Division Algorithm](https://lightmysky.com/learn/mathematics/divisibility-and-the-division-algorithm-mt_UkQNs-6-40) - [Equivalence Relations and Partitions](https://lightmysky.com/learn/mathematics/equivalence-relations-and-partitions-mt_wgEupYwEUF)