Tricki
a repository of mathematical know-how

Strengthen your inductive hypothesis

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.

Quick description

Suppose that you are trying to prove by induction that the statement P(n) holds for every positive integer n, and suppose that you are having difficulties deducing P(n) from P(n-1). One option you have is to work on a different statement Q(n). If Q(n) implies P(n) and if Q(n) can be proved by induction, then you have proved P(n). This often turns out to be a very helpful technique.

Prerequisites

Basic graph theory.

Example 1: Proof that all planar graphs are 5-choosable

General discussion