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

Revision Note

Test yourself

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

Author: Dan