--- 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-09-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 An induction proof settles a claim for every whole number from some starting point. It has three parts: a base case, an inductive hypothesis, and an inductive step. The hypothesis assumes the claim for some case k so the step can climb to k plus 1. A classic target is the sum 1 plus 2 up to n equals n times n plus 1 over 2. The base case checks n equal to 1, where both sides equal 1. **Example.** Assume 1 plus 2 up to k equals k times k plus 1 over 2. Add k plus 1 to both sides. The left side becomes the sum up to k plus 1. The right side becomes k times k plus 1 over 2 plus k plus 1, which simplifies to k plus 1 times k plus 2 over 2. That is exactly the formula with k plus 1 in place of k. 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. **Tip.** 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. **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 - [Arithmetic Series and Sigma Notation](https://lightmysky.com/learn/mathematics/arithmetic-series-and-sigma-notation-mt_bAIPng87JO) - [Sets and Functions in the Language of Proof](https://lightmysky.com/learn/mathematics/sets-and-functions-in-the-language-of-proof-mt_XAcHX_3DVz) ## Opens up - [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8) - [Loop Invariants and Proving an Algorithm Correct](https://lightmysky.com/learn/computing/loop-invariants-and-proving-an-algorithm-correct-mt_fWnstju2ns) - [Trees and Spanning Trees](https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ) - [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)