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 is the position-to-term formula for the recursive sequence :
- Show the result is true for the base case
- STEP 2: The assumption step
- Assume the result is true for n = k for some integer k
- For example: Assume is true
- There is nothing to do for this step apart from writing down the assumption
- Assume the result is true for n = k for some integer k
- 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
- The trick to this step is to use the recursive relation formula:
- 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 for .
Prove by mathematical induction that for .