Proof by induction

How it is used

The two parts are the 'base case' and the 'inductive step', in which you use the 'inductive hypothesis'. Exams often use it for formulas such as 1 + 2 + … + n = n(n + 1)/2. It is also called 'mathematical induction'.

Example sentences

1. Use proof by induction to show that 1 + 3 + 5 + … + (2n − 1) = n².

2. In a proof by induction, don't forget to check the base case.

Common collocations

• proof by induction
• base case
• inductive step
• inductive hypothesis
• mathematical induction

Related terms

• proofA logical argument that shows, step by step from accepted facts, that a mathematical statement is always true.
• integerA whole number that can be positive, negative or zero, such as −3, 0 or 25, with no fractional or decimal part.
• proof by contradictionA method of proof in which you assume the statement is false and show that this leads to something impossible, so the statement must be true.
• QEDShort for the Latin 'quod erat demonstrandum', meaning 'which was to be shown'; written at the end of a proof to show that it is complete.

More terms: Proofs and Mathematical Writing

• theorem
• let x be
• counterexample
• lemma
• without loss of generality
• it follows that