Proof By Induction

Question 1

What are the steps for proof by induction - summing an infinite series?

Answer 1

1. Check the base case for n=1 by subbing 1 into everywhere there is an n
2. Assume the result is true for n=k by subbing k into everywhere there is an n
3. Write down a target for n=k+1 by subbing k+1 into everywhere there is an n
4. Solve when n=k+1 using the result Σ^k+1_r=1 f(r) = Σ^k_r=1 f(r) + f(k+1)
   Where f(r) is your function of r
5. Write your standard statement

Question 2

What is the standard statement in proof by induction?

Answer 2

We have shown that if the result is true for n=k then it is true for n=k+1 and as it is true for n=1 it is true for all positive integers n

Question 3

What are the steps for proof by induction - divisibility?

Answer 3

1. Let f(n) be the expression you are trying to prove is divisible by a given number
2. Check that that f(n) is divisible by the given number when n=1
3. Assume that f(k) is divisible by the given number
4. Now write out f(k+1) and try to rearrange to get f(k+1) in terms of f(k) and a term divisible by the given number
5. Write out your standard statement

Question 4

What are the steps for proof by induction - powers of matrices? Where Mⁿ = result

Answer 4

1. Check that the result is true for n=1 by subbing 1 into everywhere there is an n
2. Assume the result is true for n=k by subbing a k into everywhere there is an n
3. Write down your target for n=k+1 by subbing k+1 into everywhere there is an n
4. Write M^k+1 as MⁿM (not using the result)
5. Multiply out the matrices until you reach your target
6. Write your standard statement

Question 5

What if you are asked to prove something for n≥0

Answer 5

Check the base case as 0 instead of 1 then do the proof as normal using k and k+1

Question 6

What are the steps for proof by induction - general term of a sequence?
These questions are normally given in the form recursive definition-what the first term should equal-result

Answer 6

1. Check that the result is true for n=1 by subbing 1 into the result and seeing if it equals the given value for the first term
2. Assume the result is true for n=k by subbing in k whererver there is an n in the result
3. Write down your target for n=k+1 by subbing in k+1 wherever there is an n in the result
4. Using the recursive defintion write u_k+1 in terms of u_k and rearrange until you get to your target
5. Write the standard statement

Question 7

What do you do if you are given two base cases instead of one? (stronger induction)

Answer 7

1. Check the base cases for n=1 and n=2
2. Assume the result is true for n=k and n=k+1
3. Prove the result is true for n=k+2
4. Write the adjusted statement: We have shown that if the result is true for n=k and n=k+1 then it is true for n=k+2 and as the result is true for n=1 and n=2 the result is true for all positive integers n

Question 8

If you are given a different kind of proof by induction (other types) what are the general steps?

Answer 8

1. Check that the result is true for n=1
2. Assume the result is true for n=k
3. Using your assumption show the result is true for n=k+1
4. Write the standard statement