Induction path · D02

Before this lesson: Why mathematical induction works, Algebraic identities and factorisation, Divisibility of integers

Your goal: Write a complete induction proof with a valid starting index.

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.

Mathematical Induction: Steps and Solved Examples: the key idea

Weak induction has two obligations: prove P(n₀), then show for each integer k≥n₀ that P(k) implies P(k+1). In the step, assume precisely P(k), not the desired result P(k+1). Write the next expression, separate its new term and insert the hypothesis. For inequalities, check the sign of every multiplier and the starting index. If the claim begins at n=4, the base n=1 is irrelevant. The proof should end by invoking induction for the stated domain.

A worked example

Prove 1+3+⋯+(2n−1)=n² for n≥1.

At n=1, 1=1². Assume the formula at k. Adding the next odd term 2k+1 gives k²+2k+1=(k+1)². Therefore the claim follows for every n≥1.

Your turn: change one thing

Prove 7n−17^{n}-1 is divisible by 6 for every n≥1.

Try this on paper before opening the explanation.

Compare your reasoning

Base: 7−1=6. If 7k−1=6m7^{k}-1=6m, then 7k+1−1=7(7k−1)+6=6(7m+1)7^{k+1}-1=7(7^{k}-1)+6=6(7m+1). This proves the step.

Pause and check

A trap to avoid: Assuming the very statement being proved or omitting the base case.

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 2n≥n+12^{n}\ge n+1 for every integer n≥0.

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

At n=0 both sides are 1. Assume 2k≥k+12^{k}\ge k+1 with k≥0. Multiplication by 2 gives 2k+1≥2k+2≥k+22^{k+1}\ge 2k+2\ge k+2, because k≥0. This is P(k+1), so 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. In the inductive step, what may be assumed?

Foundation

  1. The whole theorem
  2. Any stronger statement
  3. P(k)
  4. P(k+1)
Hint

Use only the declared induction hypothesis.

Answer and reasoning

P(k). The goal is to derive P(k+1) from P(k).

2. For a claim starting at n=4, the natural base case is what?

Foundation

  1. n=4
  2. n=0
  3. n=1
  4. n=5
Hint

Use the first allowed index.

Answer and reasoning

n=4. The induction chain must begin at 4.

3. After the first k odd numbers, the next term is what?

Core

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

Substitute k+1 into 2n−1.

Answer and reasoning

2k+1. 2(k+1)−1=2k+1.

4. In the divisibility proof, 7k+1−17^{k+1}-1 equals what?

Core

  1. 7(7k−1)7(7^{k}-1)
  2. 7k+67^{k}+6
  3. 6(7k−1)6(7^{k}-1)
  4. 7(7k−1)+67(7^{k}-1)+6
Hint

Expand the proposed expression.

Answer and reasoning

7(7k−1)+67(7^{k}-1)+6. 7(7k−1)+6=7k+1−7+6=7k+1−17(7^{k}-1)+6=7^{k+1}-7+6=7^{k+1}-1.

5. What is wrong with assuming P(k+1) to prove P(k+1)?

Stretch

  1. Only the base case is missing
  2. It proves a stronger theorem
  3. It is circular
  4. Nothing
Hint

The conclusion has been assumed.

Answer and reasoning

It is circular. The inductive hypothesis must concern already justified preceding information.

6. Why does 2k+2≥k+2 in the proof of 2n≥n+12^{n}\ge n+1?

Stretch

  1. k≥0
  2. k≤0
  3. k is prime
  4. 2k=k2^{k}=k
Hint

Subtract k+2.

Answer and reasoning

k≥0. The difference is k, nonnegative on the induction domain.

7. The base case does what?

Foundation

  1. Replaces the induction hypothesis
  2. Assumes the conclusion at every n
  3. Starts the chain of true statements
  4. Proves all steps by itself
Hint

Truth needs an initial established case.

Answer and reasoning

Starts the chain of true statements. The inductive implication then propagates that truth.

8. If 1+⋯+k=k(k+1)/2, adding k+1 gives what?

Core

  1. (k+1)(k+2)/2
  2. k(k+2)/2
  3. k²+1
  4. (k+1)²
Hint

Factor k+1.

Answer and reasoning

(k+1)(k+2)/2. k(k+1)/2+(k+1)=(k+1)(k/2+1).

9. If a step only proves P(k)⇒P(k+2), one base case covers what?

Stretch

  1. No indices ever
  2. Only prime indices
  3. Only one parity of indices
  4. All indices automatically
Hint

The chain advances by two.

Answer and reasoning

Only one parity of indices. A second starting case is generally needed to cover the other parity.

Choose your next step

Continue to Strong induction. 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.