1.1-2 Proof by induction recap

Question 1

How is induction like proof by programming? (What are the two subroutines)

Answer 1

Question 2

How does the induction hypothesis work

Answer 2

Assuming P(0) (base case) P(1), … P(n) is true, use that to prove P(n+1)

Question 3

How does strong induction differ

Answer 3

• In normal induction P(n) is used to prove P(n+1)
• Using strong induction P(0)…P(n) can be used to prove P(n+1)
• Same logic
• Useful for recursive functions