MATH11121 Chap.7 Induction and Strong Induction
Induction and Strong Induction
Induction and Strong Induction proves statements across ordered integer cases. The base verifies the first permitted index, the hypothesis supplies established information, and the step derives the next case. Strong induction makes all earlier cases available when a recurrence or factorisation needs more than the immediately preceding one.
What this chapter covers
- 01
Base case
- 02
Inductive hypothesis
- 03
Inductive step
- 04
Target at k+1
- 05
Strong induction
- 06
Recursive sequences
Worked example · free
Prove an odd-number sum
- 1Verify the identity at the first index.
- 2Assume the sum through the kth odd number equals k squared.
- 3Add 2k+1 and simplify to (k+1) squared before concluding.
Key terms
- Base case
- The first verified index that starts an induction chain.
- Inductive step
- The argument deriving the next case from permitted earlier cases.
- Strong induction
- An induction form that assumes all established cases through the current index.
Induction and Strong Induction FAQ
Why must the base match the stated range?
The induction chain starts at the first index covered by the theorem. Checking an earlier unrelated value does not establish that first required case or connect it to later cases.
Can I assume the k plus one case?
No. The step may assume the permitted earlier case or cases, but assuming the target P(k+1) would be circular. The proof must derive that target from the hypothesis.
When is strong induction helpful?
Use it when the next case depends on several earlier values or on a factorisation into smaller cases. The argument should still identify exactly which earlier statements are used.
Why write P of k plus one before calculating?
The explicit target shows how bounds, final terms and exponents change in the next case. It guides factorisation and prevents a correct use of the hypothesis from ending at a related expression that does not actually establish the required statement.
Can a valid inductive step prove a false theorem?
A transition may correctly show that one true case would imply the next, yet prove nothing if the required base is false or absent. Both the starting point and the universal step are necessary to create a chain of established cases.
How many base cases does strong induction need?
Use enough initial cases to support the first application of the recurrence or decomposition in the inductive step. The method does not prescribe one fixed number; the theorem's starting index and backward dependencies determine it.
Exam move
Write induction proofs in four labelled blocks: proposition P(n), base case, inductive hypothesis and inductive step. Copy the theorem range accurately so the base starts at the correct index. Before calculating, write the complete target P(k+1), including changed bounds and final terms. In sum problems, split the k+1 expression into the established sum plus one new term.
In inequalities, note where positivity or the allowed range is used. For strong induction, state the entire assumed range and mark the specific earlier cases needed by the transition. Check whether several base cases are required before the first recurrence step is legal. Keep an error log for wrong base, circular assumption, off-by-one final term and algebra that never reaches the target form.
Practise identifying false induction arguments as well as writing valid ones. The closing sentence should quantify the final result over the original range. Pattern checking may motivate a formula, but only the verified base and universal transition establish it.
Build an induction template using blank spaces rather than memorised sentences: the first index, the exact statement P(n), the assumed range for k and the desired P(k+1). Fill the template from each new theorem before doing algebra. For sums, write the kth sum in a box and attach the new last term outside it. For products, identify the new factor.
For recursively defined sequences, list which previous terms the recurrence actually uses. Test the base cases numerically and verify that the first transition references only defined earlier values. Practise examples starting at indices other than one so the base does not become automatic.
Add false proofs to revision: a valid step with a false base, a correct base with a circular step, and a step proved only for one special k. Diagnose exactly why each argument fails. In inequality induction, mark every place where multiplying or adding preserves the inequality and justify sign conditions. In divisibility induction, aim the final expression at a multiple of the stated divisor.
Strong induction should list all assumed cases but also name the particular cases used; extra assumptions do not remove the need for a transparent transition. After a complete proof, substitute a small later value into the formula as an error check, while recognising that this check is not part of the proof.
End by reading the quantifiers in the conclusion and confirming that the verified chain begins at the theorem's stated first value.
Working through Induction and Strong Induction in MATH11121? Sia is AskSia’s AI Mathematics tutor — ask any MATH11121 Induction and Strong Induction question and get a clear, step-by-step explanation grounded in how MATH11121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.