Problem Solving

Induction Hypothesis

Students point to an earlier domino before setting up the next.

Induction Hypothesis definition

An induction hypothesis is the earlier case or cases temporarily assumed true inside an inductive step.

In Spanish
hipótesis de inducción
Topic
Proof techniques

Induction Hypothesis in a picture

Induction Hypothesis diagramThe hypothesis P(k) is used inside the proof of the next statement P(k + 1).Choose an arbitrary kKeep k in the allowed rangeTemporarily assume P(k)This is the induction hypothesisDerive P(k + 1)This proves the required implication
The hypothesis P(k) is used inside the proof of the next statement P(k + 1).

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

Which statement is assumed in ordinary induction?

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.