Induction path · D03

Before this lesson: Mathematical induction: the first principle, Prime numbers

Your goal: Choose a sufficient induction hypothesis and justify every smaller case used.

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.

Names you may know: complete induction.

Strong induction: the key idea

Strong induction permits the hypothesis P(n₀),P(n₀+1),…,P(k) when proving P(k+1). It is useful when the next object splits into smaller pieces whose sizes are not necessarily k. The logic is equivalent in strength to weak induction, but the form fits factorisation and recurrences better. Include enough base cases for every backward reference. When splitting an integer, show the factors or pieces lie inside the already established range.

A worked example

Prove every integer n≥2 is a product of primes.

Base 2 is prime. Suppose the claim holds for 2,…,k and consider k+1. If it is prime, it already is a product of one prime. Otherwise k+1=ab with 2≤a,b≤k. The hypothesis factors both a and b into primes; multiplying their factorizations proves the claim.

Your turn: change one thing

Why does this proof establish existence but not uniqueness of prime factorisation?

Try this on paper before opening the explanation.

Compare your reasoning

It constructs a prime factorisation for every integer, but does not compare two possible factorizations. Uniqueness needs an additional argument such as Euclid’s lemma.

Pause and check

A trap to avoid: Using a smaller case below the proven starting range.

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

Prove every integer n≥8 can be written 3a+5b with nonnegative integers a,b.

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

Bases: 8=3+5, 9=3·3, 10=5·2. For n≥11, n−3≥8. Assume the representation exists for all integers from 8 to n−1. Then n−3=3a+5b, so n=3(a+1)+5b. The coefficients remain nonnegative. Strong induction completes the proof.

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. Strong induction may use which assumptions for the next case?

Foundation

  1. All later cases
  2. No base cases
  3. Only false cases
  4. All preceding cases in the proved range
Hint

Its hypothesis includes the earlier range.

Answer and reasoning

All preceding cases in the proved range. It can use any earlier index already covered by the induction.

2. Is strong induction logically stronger than weak induction?

Foundation

  1. Yes, it proves false claims
  2. Yes, no base is needed
  3. They apply to different number systems
  4. No, the principles are equivalent
Hint

One can encode all earlier claims into one statement.

Answer and reasoning

No, the principles are equivalent. The formulations are equivalent, though one may be more convenient.

3. If n=ab is composite with 1<a,b<n, why can the hypothesis apply?

Core

  1. a=b always
  2. n must be odd
  3. Both factors are smaller allowed integers
  4. Both are already prime
Hint

Check the range, not primality.

Answer and reasoning

Both factors are smaller allowed integers. The smaller factors lie among the earlier indices.

4. For the 3a+5b representation of all n≥8 using n−3, which base set works?

Core

  1. 9 only
  2. 1,2,3
  3. 8,9,10
  4. 8 only
Hint

Cover each residue class modulo 3.

Answer and reasoning

8,9,10. Three consecutive initial cases allow steps that add 3.

5. A prime factorisation existence proof alone establishes what?

Stretch

  1. A bound of two factors
  2. At least one prime factorisation
  3. Uniqueness automatically
  4. That n is prime
Hint

Separate existence from uniqueness.

Answer and reasoning

At least one prime factorisation. Constructing a representation does not rule out other representations.

6. Why must n−3≥8 in the representation step?

Stretch

  1. Negative coefficients are required
  2. The induction hypothesis begins at 8
  3. 8 is prime
  4. 3 is larger than 8
Hint

Stay within the proved domain.

Answer and reasoning

The induction hypothesis begins at 8. Using an index below the starting range would leave the step unjustified.

7. Strong induction is especially useful when an object splits into what?

Foundation

  1. Only an identical copy
  2. Objects larger than itself
  3. No smaller cases
  4. Several smaller objects of varying sizes
Hint

The hypothesis covers all earlier sizes.

Answer and reasoning

Several smaller objects of varying sizes. A decomposition need not use only the immediately previous index.

8. Write 11 as 3a+5b with a,b nonnegative integers.

Core

  1. a=0,b=2
  2. a=2,b=1
  3. a=1,b=2
  4. a=3,b=1
Hint

Try one copy of 5.

Answer and reasoning

a=2,b=1. 11−5=6=3·2.

9. Why are three initial cases used for a step subtracting 3?

Stretch

  1. Because every proof needs three cases
  2. Because there are three variables
  3. To start all three residue classes modulo 3
  4. Because 3 is prime
Hint

Repeatedly adding 3 preserves the residue class.

Answer and reasoning

To start all three residue classes modulo 3. Three consecutive bases cover every possible remainder.

Choose your next step

Try a written problem in the challenge room. 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.