Induction path · D01

Before this lesson: How to write a proof, Sequences and sums

Your goal: Distinguish a conjecture from a proof covering all admissible integers.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Why Mathematical Induction Works: the key idea

A sequence of successful examples suggests a conjecture but does not prove a statement for every integer. Mathematical induction is a method for statements P(n) indexed by integers n≥n₀. A proof needs both an initial case and a rule that carries truth from an allowed index to the next. Write P(n) precisely before beginning, including its starting index. A counterexample can disprove a universal claim immediately, whereas many confirming cases cannot establish it.

A worked example

The numbers n²+n+41 are prime for n=0,1,2. Does this prove they are always prime?

No. At n=41 the value is 41²+41+41=41·43, which is composite. A finite list of primes cannot establish a universal claim.

Your turn: change one thing

Write a precise induction statement for the sum of the first n odd numbers.

Try this on paper before opening the explanation.

Compare your reasoning

For every integer n≥1, P(n) is 1+3+⋯+(2n−1)=n². The domain and the final term are both explicit.

Pause and check

A trap to avoid: Believing several numerical checks prove an infinite claim.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Explain why checking one thousand cases does not prove a claim for every positive integer.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

The checked indices form a finite set, while the positive integers have no largest element. Without an argument covering the remaining indices, a failure could occur later. Induction supplies such an argument through an initial case and a universal implication P(k)⇒P(k+1).

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. Which evidence proves a universal claim?

Foundation

  1. A valid argument covering every allowed case
  2. Ten examples
  3. A graph alone
  4. A likely pattern
Hint

Examples do not exhaust an infinite domain.

Answer and reasoning

A valid argument covering every allowed case. A universal proof must justify all allowed inputs.

2. An induction statement should specify what?

Foundation

  1. Only the answer for n=1
  2. A decimal approximation
  3. The integer domain and starting index
  4. Only a diagram
Hint

Decide exactly which P(n) is being proved.

Answer and reasoning

The integer domain and starting index. A starting index determines the first case and the range of the inductive implication.

3. For n=41, n²+n+41 equals which factorisation?

Core

  1. 43·43
  2. 41·43
  3. 41·41
  4. 41·42
Hint

Factor out 41.

Answer and reasoning

41·43. 41²+41+41=41(41+2)=41·43.

4. The nth positive odd number is what?

Core

  1. 2n
  2. n²
  3. n+1
  4. 2n−1
Hint

Check n=1 and the step size 2.

Answer and reasoning

2n−1. The sequence 1,3,5,… has term 1+2(n−1)=2n−1.

5. If a conjecture fails at one permitted input, what follows?

Stretch

  1. The domain is irrelevant
  2. The universal conjecture is false
  3. Most cases prove it true
  4. Induction repairs it automatically
Hint

Universal means every allowed input.

Answer and reasoning

The universal conjecture is false. One counterexample negates a universal claim.

6. Why is P(k)⇒P(k+1) alone insufficient?

Stretch

  1. k must be even
  2. It needs a true starting case
  3. It needs every case checked separately
  4. Implications cannot prove anything
Hint

An unstarted chain has no established true term.

Answer and reasoning

It needs a true starting case. The implication transmits truth but does not provide the initial truth.

7. A conjecture is best described as what?

Foundation

  1. A proved theorem by definition
  2. A false statement always
  3. A numerical answer only
  4. A proposed statement awaiting proof or disproof
Hint

Evidence may suggest it without proving it.

Answer and reasoning

A proposed statement awaiting proof or disproof. A conjecture expresses a pattern believed to hold but not yet established.

8. The sum of the first four positive odd numbers is what?

Core

  1. 15
  2. 10
  3. 8
  4. 16
Hint

Add 1,3,5,7.

Answer and reasoning

16. Their sum is 16=4².

9. Why does a counterexample need to belong to the stated domain?

Stretch

  1. Outside values are always valid
  2. Domains are optional
  3. The claim makes no assertion outside that domain
  4. Every domain is ℝ
Hint

A universal statement quantifies only over allowed inputs.

Answer and reasoning

The claim makes no assertion outside that domain. A failure outside its domain does not refute it.

Choose your next step

Continue to Mathematical induction: the first principle. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.