Common Cases of Proof by Induction (Edexcel A Level Further Maths: Core Pure)

Revision Note

Author

Dan

Last updated

29 August 2022

Proof by Induction - Sequences

What are the steps for proof by induction with sequences?

STEP 1: The basic step
- Show the result is true for the base case
  - If the recursive relation formula for the next term involves the previous two terms then you need to show the position-to-term formula works the first two given terms which will be given as part of the definition of the sequence
- This is normally n = 1 or 0 but it could be any integer
  - For example: To prove $u_{n} = 3^{n} - 2$ is the position-to-term formula for the recursive sequence $u_{n + 1} = 3 u_{n} + 4, u_{1} = 1$ :
  - $u_{1} = 3^{1} - 2 = 1$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $u_{k} = 3^{k} - 2$ 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 write down what you want to show
- The assumption from STEP 2 will be needed at some point
  - For example: Want to show $u_{k + 1} = 3^{k + 1} - 2$
- The trick to this step is to use the recursive relation formula:
  - $u_{k + 1} = 3 u_{k} + 4$

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

Worked example

A sequence is defined by $u_{n + 1} = 5 u_{n} - 4, u_{1} = 2$ for $n \geq 1$ .

Prove by mathematical induction that $u_{n} = 5^{n - 1} + 1$ for $n \geq 1$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-sequences-we

Proof by Induction - Series

What are the steps for proof by induction with series?

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)$
- The trick to this step is to use:

$\sum_{r = 1}^{k + 1} f (r) = f (k + 1) + \sum_{r = 1}^{k} f (r)$

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

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 - Divisibility

What are the steps for proof by induction with series?

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 $f (n) = 4^{n} - 1$ is divisible by 3 for all integers n ≥ 1 you would first need to show it is true for n = 1:
  - $f (1) = 4 - 1 = 3 = 3 (1)$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $f (k) = 4 - 1$ is divisible by 3
- There is nothing to do for this step apart from writing down the assumption
- The trick for this step is to write the expression as a multiple of the number
  - For example: $4^{k} - 1 = 3 p$ for some integer p
STEP 3: The inductive step
- Using the assumption show the result is true for n = k + 1
- The assumption from STEP 2 will be needed at some point
  - For example: Show that $f (k + 1) = 4^{k + 1} - 1$ is divisible by 3
- The trick to this step is to use:

$a^{k + 1} = a \times a^{k}$

- - For example: $f (k + 1) = 4 (4^{k}) - 1 = 4 (1 + 3 p) - 1 = 3 (p + 1)$
- Another trick is to show that $f (k + 1) - f (k)$ is divisible by the number
- Be careful with numbers like 6 as for these you can instead show it is divisible by both 3 and 2

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

Worked example

Prove by induction that $f (n) = 6^{n} + 13^{n + 1}$ is divisible by 7 for all integers $n \geq 0$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-divisibility-we

Proof by Induction - Matrices

What are the steps for proof by induction with matrices?

STEP 1: The basic step
- Show the result is true for the base case
- This is normally n = 1 but it could be any integer
  - For example: To prove $M^{n} = (\begin{matrix} 2^{n} & 0 \\ 1 - 2^{n} & 1 \end{matrix})$ where $M = (\begin{matrix} 2 & 0 \\ - 1 & 1 \end{matrix})$ for $n \geq 1$ :
  - $(\begin{matrix} 2^{1} & 0 \\ 1 - 2^{1} & 1 \end{matrix}) = (\begin{matrix} 2 & 0 \\ - 1 & 1 \end{matrix})$
STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
  - For example: Assume $M^{k} = (\begin{matrix} 2^{k} & 0 \\ 1 - 2^{k} & 1 \end{matrix})$ 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 write down what you want to show
- The assumption from STEP 2 will be needed at some point
  - For example: Want to show $M^{k} = (\begin{matrix} 2^{k + 1} & 0 \\ 1 - 2^{k + 1} & 1 \end{matrix})$
- The trick to this step is to use write:
  - $M^{k + 1} = M M^{k}$
  - The entries in the matrix can get messy so it can be clearer to write $M^{k + 1} = (\begin{matrix} a & b \\ c & d \end{matrix})$ and then find expressions for a, b, c, d on separate lines

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

Worked example

The matrix $M$ is given by $M = (\begin{matrix} 2 & 2 \\ 0 & 1 \end{matrix})$ .

Prove, using mathematical induction, that $M^{n} = (\begin{matrix} 2^{n} & 2 (2^{n} - 1) \\ 0 & 1 \end{matrix})$ .

9-1-2-edexcel-al-fm-cp-proof-by-induction-matrices-we

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

the (exam) results speak for themselves:

Test yourself

Did this page help you?

Previous:9.1.1 Intro to Proof by Induction

Common Cases of Proof by Induction (Edexcel A Level Further Maths: Core Pure)

Revision Note

What are the steps for proof by induction with sequences?

What are the steps for proof by induction with series?

What are the steps for proof by induction with series?

What are the steps for proof by induction with matrices?

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. Complex Numbers

1.1 Complex Numbers & Argand Diagrams

1.1.1 Introduction to Complex Numbers

1.1.2 Solving Equations with Complex Roots

1.1.3 Modulus & Argument

1.1.4 Modulus-Argument Form

1.1.5 Loci in Argand Diagrams

1.1.6 Regions in Argand Diagrams

1.2 Exponential Form & de Moivre's Theorem

1.2.1 Exponential Form

1.2.2 de Moivre's Theorem

1.2.3 Applications of de Moivre's Theorem

1.2.4 Roots of Complex Numbers

2. Matrices

2.1 Properties of Matrices

2.1.1 Introduction to Matrices

2.1.2 Determinants of Matrices

2.1.3 Inverses of Matrices

2.2 Transformations using Matrices

2.2.1 Transformations using a Matrix

2.2.2 Geometric Transformations with Matrices

2.2.3 Invariant Points & Lines

3. Further Algebra & Functions

3.1 Roots of Polynomials

3.1.1 Roots of Polynomials

3.1.2 Linear Transformations of Roots

3.2 Series

3.2.1 Sums of Integers, Squares & Cubes

3.2.2 Method of Differences

3.3 Maclaurin Series

3.3.1 Maclaurin Series

4. Hyperbolic Functions

4.1 Hyperbolic Functions

4.1.1 Hyperbolic Functions & Graphs

4.1.2 Logarithmic Forms of Inverse Hyperbolic Functions

4.1.3 Hyperbolic Identities & Equations

4.1.4 Differentiating & Integrating Hyperbolic Functions

5. Further Calculus

5.1 Volumes of Revolution

5.1.1 Volumes of Revolution

5.1.2 Modelling with Volumes of Revolution

5.2 Methods in Calculus

5.2.1 Improper Integrals

5.2.2 Mean Value of a Function

5.2.3 Integrating with Partial Fractions

5.2.4 Calculus involving Inverse Trig

5.2.5 Integration by Substitution

6. Further Vectors

6.1 Vector Lines

6.1.1 Equations of Lines in 3D

6.1.2 Pairs of Lines in 3D

6.1.3 Angle between Lines

6.1.4 Shortest Distances - Lines

6.2 Vector Planes

6.2.1 Equations of planes

6.2.2 Combinations of Lines & Planes

6.2.3 Combinations of Planes

6.2.4 Shortest Distances - Planes

7. Polar Coordinates

7.1 Polar Coordinates

7.1.1 Polar Coordinates

7.1.2 Calculus with Polar Coordinates

8. Differential Equations

8.1 First Order Differential Equations

8.1.1 Intro to Differential Equations

8.1.2 Solving First Order Differential Equations

8.1.3 Modelling using First Order Differential Equations

8.2 Second Order Differential Equations

8.2.1 Solving Second Order Differential Equations

8.2.2 Coupled First Order Linear Equations

8.3 Simple Harmonic Motion