Core Pure - Proof By Induction

Question 1

What 3 things might you be asked to use proof by induction to prove?

Answer 1

Summation
Division
Matrices

Question 2

How many steps are there for proof by induction?

Answer 2

4

Question 3

What are the different names of the different steps in proof by induction?

Answer 3

1 - Basis
2 - Assumption
3 - Inductive
4 - Conclusion

Question 4

Explain the first step in proof by induction?

Answer 4

You prove that when n=1 the statement is true

Method -
State: let n=1
Then substitute n=1 into the LHS and the RHS
Do simple algebra
State: As LHS=RHS, the … is true for n=1

Question 5

Explain the second step in proof by induction?

Answer 5

State: Assume the … is true for n=k

State the … in the question but substituting in n=k

Question 6

Explain the third step in proof by induction?

Answer 6

You substitute n=k+1
Use the special rule for either the matrix, division or summation method
Do algebra to rewrite the expression as the expected result
State: Therefore the … formula is true for k+1

Question 7

Explain the forth step in proof by induction?

Answer 7

You need to regurgitate a special conclusion which is unique for each of the 3 different questions

Question 8

Which step is exactly the same for every question?

Answer 8

Step 2 which is about assuming the statement is true for all k and then rewriting the question in terms of k

Question 9

How is step 1 in proof by induction of division slightly different?

Answer 9

At the end you need to show that xy is divisible by x by taking out a factor of x [(x)(y)]
Then state:f(n) is divisible by x when n=1

Question 10

What is the special rule for proof by induction: summation?

Answer 10

When substituting n=k+1 into the summation
You can rewrite the summation as the summation with k not k+1 at the top + the (k+1)th term (which will just be the summation formula with r substituted for k+1)

Question 11

What is the special rule for proof by induction: division?

Answer 11

With the stated function in the question being f(n)
And you assumed that it is true for f(k)
You want to show that f(k+1) - f(k) is a multiple of …

Question 12

What is the special rule of proof by induction: matrices?

Answer 12

Question 13

What is the symbol for the set of all positive integers?

Answer 13

Question 14

What does this symbol mean?

Answer 14

The set of all positive integers

Question 15

What is the conclusion statement for proof by induction: summation?

Answer 15

If the summation formula is true for n=k then it is shown to be true for n=k+1. As the result is true for n=1, it is now also true for all positive integers,n, by mathematical induction

(Use the better way to write all positive integers)

Question 16

What is the conclusion statement for proof by induction: division?

Answer 16

If f(n) is divisible by 3 when n=k, then it has been shown that f(n) is also divisible by 3 when n=k+1. As f(n) is divisible by 3 when n=1, f(n) is also divisible by 3 for all …….. by mathematical induction

Question 17

What is the conclusion statement for proof by induction: matrix?

Answer 17

If the matrix equation is true for n=k, then it is shown to be true for n=k+1. As the matrix equation is true for n=1, it is also true for all ….. by mathematical induction

Question 18

What do you often forget to do in step 3 of proof by induction?

Answer 18

State: therefore the … is true when n=k+1

Question 19

What is a really useful thing to do in proof by induction?

Why is this useful?

Answer 19

At the top of the question write out the desired result and maybe the next step

This is useful because you can easily check where the end goal is
Often the very last step involves completely non intuitive maths so it is useful to know when you have reached that step

Question 20

What is meant by “desired result”?

Answer 20

For summation and Matrix questions the question will state a statement to prove but it is in terms of n

The desired result is on the RHS and you just need to replace n with k+1

Don’t simplify the expression. Parts of it may be like 2(k+1)+1. Thats normal.

Question 21

What is important to remember when doing the matrices proof?

Answer 21

In the inductive step:

Question 22

What is a common mistake that you make in he matrices questions?

Answer 22

I use n not k in the inductive step