Induction and Recursion

Question 1

What is the template for mathematical induction

Answer 1

1. Express the statement that is to be proven in the form
2. Write out the words basis step and show that p(b) is true
3. Write out the words inductive step
4. Statte and clearly identify the inductive step
5. State what needs to be proven under the assumption that the inductive hypothesis is true
6. Prove the statement P(k+1)
7. Clearly identify the conclusion
8. After completing the basis step and the inductive step, state that “by mathematical induction, P(n) is true for all integers n with n › b”.

Question 2

What is the basis step