Induction Hypothesis definition
An induction hypothesis is the earlier case or cases temporarily assumed true inside an inductive step.
Induction Hypothesis in a picture
How it works
In ordinary induction, assume P(k) for an arbitrary allowed k and use it to prove P(k + 1). In strong induction, the assumption can include all earlier cases. The argument proves an implication, which is combined with the base case.
Worked examples
For a sum identity, what can you assume at stage k?
Assume the identity is true for the sum through k.
In strong induction proving P(8), what may be assumed if the range starts at 1?
P(1) through P(7).
Can you assume P(k + 1) to prove P(k + 1)?
No. That is the conclusion of the step.
Common mistake
Treat the assumption as temporary and keep the earlier index distinct from the target index.
Quick check
Does the hypothesis replace the base case?
Show answer
No.
Can the hypothesis in strong induction involve multiple indices?
Show answer
Yes.
Sources
Flashcard
Induction Hypothesis
Reveal the definition
An induction hypothesis is the earlier case or cases temporarily assumed true inside an inductive step.
Effortless Math. “Induction Hypothesis.” Math Dictionary.
