Proof by Induction

What is proof by induction?

Proof by induction is a way of proving a result is true for a set of integers by showing that if it is true for one integer then it is true for the next integer
It can be thought of as dominoes:

All dominoes will fall down if:

The first domino falls down
Each domino falling down causes the next domino to fall down

What are the steps for proof by induction?

STEP 1: The basic step

Show the result is true for the base case
This is normally n = 1 or 0 but it could be any integer

For example: To prove $\sum_{r = 1}^{n} r^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$ is true for all integers n ≥ 1 you would first need to show it is true for n = 1:
$\sum_{r = 1}^{1} r^{2} = \frac{1}{6} (1) ((1) + 1) (2 (1) + 1)$

STEP 2: The assumption step

Assume the result is true for n = k for some integer k

For example: Assume $\sum_{r = 1}^{k} r^{2} = \frac{1}{6} k (k + 1) (2 k + 1)$ is true

There is nothing to do for this step apart from writing down the assumption

STEP 3: The inductive step

Using the assumption show the result is true for n = k + 1
It can be helpful to simplify LHS & RHS separately and show they are identical
The assumption from STEP 2 will be needed at some point

For example: $L H S = \sum_{r = 1}^{k + 1} r^{2}$ and $R H S = \frac{1}{6} (k + 1) ((k + 1) + 1) (2 (k + 1) + 1)$

STEP 4: The conclusion step

State the result is true
Explain in words why the result is true
It must include:

If true for n = k then it is true for n = k + 1
Since true for n = 1 the statement is true for all n ∈ ℤ, n ≥ 1 by mathematical induction

The sentence will be the same for each proof just change the base case from n = 1 if necessary

What type of statements might I be asked to prove by induction?

Sums of sequences
- If the terms involve factorials then $(k + 1)! = (k + 1) \times (k!)$ is useful
- These can be written in the form $\sum_{r = 1}^{n} f (r) = g (n)$
- A useful trick for the inductive step is using $\sum_{r = 1}^{k + 1} f (r) = f (k + 1) + \sum_{r = 1}^{k} f (r)$
Divisibility of an expression by an integer
- These can be written in the form $f (n) = m \times q_{n}$ where m & q_n are integers
- A useful trick for the inductive step is using $a^{k + 1} = a \times a^{k}$
Complex numbers
- You can use proof by induction to prove de Moivre’s theorem
Derivatives
- Such as chain rule, product rule & quotient rule
- These can be written in the form $f^{(n)} (x) = g (x)$
- A useful trick for the inductive step is using $f^{(k + 1)} (x) = \frac{d}{d x} (f^{(k)} (x))$
- You will have to use the differentiation rules

Examiner Tip

Learn the steps for proof by induction and make sure you can use the method for a number of different types of questions before going into the exam
The trick to answering these questions well is practicing the pattern of using each step regularly

Worked example

Prove by induction that $\sum_{r = 1}^{n} r (r - 3) = \frac{1}{3} n (n - 4) (n + 1)$ for $n \in ℤ^{+}$ .

1-5-1-ib-aa-hl-proof-by-induction-we-solution

Proof by Induction (DP IB Maths: AA HL)

Revision Note

What is proof by induction?

What are the steps for proof by induction?

What type of statements might I be asked to prove by induction?

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

1. Number & Algebra

1.1 Number & Algebra Toolkit

1.1.1 Standard Form

1.1.2 Laws of Indices

1.1.3 Partial Fractions

1.2 Exponentials & Logs

1.2.1 Introduction to Logarithms

1.2.2 Laws of Logarithms

1.2.3 Solving Exponential Equations

1.3 Sequences & Series

1.3.1 Language of Sequences & Series

1.3.2 Arithmetic Sequences & Series

1.3.3 Geometric Sequences & Series

1.3.4 Applications of Sequences & Series

1.3.5 Compound Interest & Depreciation

1.4 Simple Proof & Reasoning

1.4.1 Proof

1.5 Further Proof & Reasoning

1.5.1 Proof by Induction

1.5.2 Proof by Contradiction

1.6 Binomial Theorem

1.6.1 Binomial Theorem

1.6.2 Extension of The Binomial Theorem

1.7 Permutations & Combinations

1.7.1 Counting Principles

1.7.2 Permutations & Combinations

1.8 Complex Numbers

1.8.1 Intro to Complex Numbers

1.8.2 Modulus & Argument

1.8.3 Introduction to Argand Diagrams

1.9 Further Complex Numbers

1.9.1 Geometry of Complex Numbers

1.9.2 Forms of Complex Numbers

1.9.3 Complex Roots of Polynomials

1.9.4 De Moivre's Theorem

1.9.5 Roots of Complex Numbers

1.10 Systems of Linear Equations

1.10.1 Systems of Linear Equations

1.10.2 Algebraic Solutions

2. Functions

2.1 Linear Functions & Graphs

2.1.1 Equations of a Straight Line

2.2 Quadratic Functions & Graphs

2.2.1 Quadratic Functions

2.2.2 Factorising & Completing the Square

2.2.3 Solving Quadratics

2.2.4 Quadratic Inequalities

2.2.5 Discriminants

2.3 Functions Toolkit

2.3.1 Language of Functions

2.3.2 Composite & Inverse Functions

2.3.3 Symmetry of Functions

2.3.4 Graphing Functions

2.4 Other Functions & Graphs

2.4.1 Exponential & Logarithmic Functions

2.4.2 Solving Equations

2.4.3 Modelling with Functions

2.5 Reciprocal & Rational Functions

2.5.1 Reciprocal & Rational Functions

2.6 Transformations of Graphs

2.6.1 Translations of Graphs

2.6.2 Reflections of Graphs

2.6.3 Stretches Graphs

2.6.4 Composite Transformations of Graphs

2.7 Polynomial Functions

2.7.1 Factor & Remainder Theorem

2.7.2 Polynomial Division

2.7.3 Polynomial Functions

2.7.4 Roots of Polynomials

2.8 Inequalities

2.8.1 Solving Inequalities Graphically

2.8.2 Polynomial Inequalities