Principle of Mathematical Induction

Principle of Mathematical Induction

What is it?

To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.

In simple words

• To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true.
• (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1).
• Then P(n) holds for all n >= n0.
• You must do both base and step. The step alone does not start the chain.

Important terms

PRINCIPLE OF MATHEMATICAL INDUCTION: To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.

1. BASE: Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

2. STEP: Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

What you should learn

• State the main ideas and notation used in principle of mathematical induction.
• Apply the rules of principle of mathematical induction in a clear, step-by-step solution.
• Check signs, conditions, and the final answer for mathematical accuracy.

Examples

• n=1 arithmetic
• Both sides numbers
• Do not skip

BASE

Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

STEP

Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

Full school-level explanation

To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.

Two doors, both needed:

WHAT — PRINCIPLE OF MATHEMATICAL INDUCTION

To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2) Step: assume P(k) (inductive hypothesis) and prove P(k+1). Then P(n) holds for all n >= n0. Meaning: knock down the first domino, and prove each knocks the next. The assumption P(k) is not the thing you want to prove; it is a tool for the next integer.

RULE — 1. BASE

Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

METHOD — 2. STEP

Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

WORKED EXAMPLE

Worked skeleton: sum of first n odds is n^2. P(n): 1+3+...+(2n-1)=n^2 base n=1: 1=1 assume up to k: sum = k^2 add next odd 2k+1: k^2+2k+1=(k+1)^2

BASE

Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed base kills the proof even if the step looks pretty.

Remember

• check the first n

Examples

• n=1 arithmetic
• Both sides numbers
• Do not skip

STEP

Write P(k): the formula with n=k. For P(k+1), start from the left side, replace using P(k), tidy to the right side of P(k+1). Say 'by IH' when you use P(k).

Remember

• IH = P(k)

Examples

• Add the next term
• Or multiply the next factor
• End at the P(k+1) formula

How to answer a principle of mathematical induction question

How it works

• Identify the given quantities, notation, and required result.
• Choose the matching rule and write it before substitution.
• Work one algebraic step at a time, keeping brackets and signs clear.
• Check restrictions, simplify the result, and verify it where possible.

Remember

• base then step
• assume P(k), prove P(k+1)
• (k+1)^2
• need the first domino
• check the first n
• IH = P(k)
• base then step
• assume P(k), prove P(k+1)

How the ideas connect

Worked skeleton: sum of first n odds is n^2. P(n): 1+3+...+(2n-1)=n^2 base n=1: 1=1 assume up to k: sum = k^2 add next odd 2k+1: k^2+2k+1=(k+1)^2

Deeper understanding

Go beyond memorising Principle of Mathematical Induction. Connect the definition to reasons, relationships, exceptions, and exam wording.

How the ideas connect

Worked skeleton: sum of first n odds is n^2. P(n): 1+3+...+(2n-1)=n^2 base n=1: 1=1 assume up to k: sum = k^2 add next odd 2k+1: k^2+2k+1=(k+1)^2

Common mistakes

Exam focus

Core Idea

1. BASE

2. STEP

Worked Example

Exam focus

Quick revision

• base then step
• assume P(k), prove P(k+1)
• (k+1)^2
• need the first domino
• PRINCIPLE OF MATHEMATICAL INDUCTION: To prove a statement P(n) for every integer n >= n0 (usually n>=1): (1) Base: show P(n0) is true. (2
• 1. BASE: Usually n=1: plug in and check a number identity. If the claim starts at n=2, start there. A failed

You must do both base and step. The step alone does not start the chain.

For long answers on Principle of Mathematical Induction: define clearly → explain the main parts → give one example → state one exam caution.