Name: Proof by Induction (1.5.1) | DP IB Maths: AA HL Revision Notes 2021 Membership
Brand: Save My Exams
Price: 60 GBP
Availability: OnlineOnly
Rating: 4.7 (1021 reviews)

1.5.1 Proof by Induction

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

Exam 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

DP IB Maths: AA HL

Revision Notes

1.5.1 Proof by Induction

Proof by Induction

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?

Exam Tip

Worked Example

Author: Daniel

Resources

Members

Company

Quick Links