Core Pure - Proof By Induction Flashcards
What 3 things might you be asked to use proof by induction to prove?
Summation
Division
Matrices
How many steps are there for proof by induction?
4
What are the different names of the different steps in proof by induction?
1 - Basis
2 - Assumption
3 - Inductive
4 - Conclusion
Explain the first step in proof by induction?
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
Explain the second step in proof by induction?
State: Assume the … is true for n=k
State the … in the question but substituting in n=k
Explain the third step in proof by induction?
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
Explain the forth step in proof by induction?
You need to regurgitate a special conclusion which is unique for each of the 3 different questions
Which step is exactly the same for every question?
Step 2 which is about assuming the statement is true for all k and then rewriting the question in terms of k
How is step 1 in proof by induction of division slightly different?
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
What is the special rule for proof by induction: summation?
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)
What is the special rule for proof by induction: division?
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 …
What is the special rule of proof by induction: matrices?
What is the symbol for the set of all positive integers?
What does this symbol mean?
The set of all positive integers
What is the conclusion statement for proof by induction: summation?
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)
What is the conclusion statement for proof by induction: division?
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
What is the conclusion statement for proof by induction: matrix?
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
What do you often forget to do in step 3 of proof by induction?
State: therefore the … is true when n=k+1
What is a really useful thing to do in proof by induction?
Why is this useful?
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
What is meant by “desired result”?
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.
What is important to remember when doing the matrices proof?
In the inductive step:
What is a common mistake that you make in he matrices questions?
I use n not k in the inductive step
